Jump Game

Medium Problem 135 of 151 Java and Python

Practice on LeetCode

Problem

You start at index 0 of an integer array nums. Each element is the maximum jump length from that position.

Return true if you can reach the last index, otherwise false.

Example 1

Input: nums = [2, 3, 1, 1, 4]
Output: true
Why: Jump 1 step to index 1, then 3 steps to the end.

Example 2

Input: nums = [3, 2, 1, 0, 4]
Output: false
Why: Every path lands on index 3, whose jump length is 0.

Constraints

1 ≤ nums.length ≤ 10⁴
0 ≤ nums[i] ≤ 10⁵

Explanation

You do not need to know which jumps to take, only how far you could get. Walk left to right keeping reach, the farthest index reachable so far. If you ever stand at an index beyond reach, you are stuck.

Approach 1 · Naive

DP: which indexes are reachable

Time O(n · max jump)
Space O(n)

Mark index 0 reachable, and from every reachable index mark all indexes within its jump length.

ok[0] = true.
For each reachable i, set ok[j] = true for j in i + 1 … i + nums[i].
Return ok[n - 1].

Java

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        boolean[] ok = new boolean[n];
        ok[0] = true;
        for (int i = 0; i < n; i++) {
            if (!ok[i]) {
                continue;
            }
            for (int j = i + 1; j <= Math.min(n - 1, i + nums[i]); j++) {
                ok[j] = true;
            }
        }
        return ok[n - 1];
    }
}

Python

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        ok = [True] + [False] * (n - 1)
        for i in range(n):
            if ok[i]:
                for j in range(i + 1, min(n, i + nums[i] + 1)):
                    ok[j] = True
        return ok[-1]

Approach 2 · Optimal

Greedy farthest reach

Time O(n)
Space O(1)

Keep the farthest reachable index while scanning; fail if the scan passes it.

reach = 0.
For each i: if i > reach, return false; set reach = max(reach, i + nums[i]).
Return true.

Java

class Solution {
    public boolean canJump(int[] nums) {
        int reach = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > reach) {
                return false;
            }
            reach = Math.max(reach, i + nums[i]);
        }
        return true;
    }
}

Python

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        reach = 0
        for i, jump in enumerate(nums):
            if i > reach:
                return False
            reach = max(reach, i + jump)
        return True

Complexity compared

Approach	Time	Space
Naive DP: which indexes are reachable	O(n · max jump)	O(n)
Optimal Greedy farthest reach	O(n)	O(1)

Key takeaways

Greedy works when a single number (here the farthest reach) summarises everything the future needs.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem