Jump Game

Medium Arrays & Hashing Greedy Original on LeetCode

Jump Game is a medium arrays & hashing problem solved with the greedy pattern. The best approach, optimal (greedy furthest reach), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (dp over reachable indices) up.

Problem

You start at index 0 of an integer array nums. The value nums[i] is the longest jump you may make from index i: from there you can move forward by any number of steps from 1 up to nums[i] (a value of 0 means you cannot move from that index).

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

Examples

Example 1

Input
nums = [1, 3, 0, 0, 1, 0]
Output
true
Why
Jump 0 -> 1, then 1 -> 4 (a jump of 3), then 4 -> 5.

Example 2

Input
nums = [2, 1, 0, 4]
Output
false
Why
Every route ends on index 2, whose value is 0, so index 3 is never reached.

Example 3

Input
nums = [0]
Output
true
Why
You already stand on the last index.

Constraints

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 10^5

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (DP over reachable indices)O(n²)O(n)
Optimal (greedy furthest reach)O(n)O(1)

1Brute force (DP over reachable indices)

TimeO(n²)Each index can mark up to n - 1 later indices.
SpaceO(n)One flag per index.

Mark index 0 as reachable. Go left to right; from every reachable index i, mark each index it can land on (i + 1 up to i + nums[i], capped at the end). The answer is whether the last index ever gets marked.

  1. reach = boolean array of size n; reach[0] = true.
  2. For each i with reach[i] true: for j from i + 1 to min(n - 1, i + nums[i]), set reach[j] = true.
  3. Return reach[n - 1].
class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        boolean[] reach = new boolean[n];
        reach[0] = true;
        for (int i = 0; i < n; i++) {
            if (!reach[i]) {
                continue;
            }
            int end = (int) Math.min(n - 1, (long) i + nums[i]);
            for (int j = i + 1; j <= end; j++) {
                reach[j] = true;
            }
        }
        return reach[n - 1];
    }
}

2Optimal (greedy furthest reach)

TimeO(n)One pass over the array.
SpaceO(1)Only the furthest reach is stored.

Because the reachable indices always form a prefix, one number describes them: far, the furthest index reachable so far. Scan left to right; if you arrive at an index beyond far, you are stuck. Otherwise extend far with i + nums[i].

  1. far = 0.
  2. For i from 0 to n - 1: if i > far, return false.
  3. far = max(far, i + nums[i]); if far >= n - 1, return true.
  4. Return true after the loop.
class Solution {
    public boolean canJump(int[] nums) {
        int far = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > far) {
                return false;
            }
            far = Math.max(far, i + nums[i]);
            if (far >= nums.length - 1) {
                return true;
            }
        }
        return true;
    }
}

Edge cases to test

  • A single element, even if it is 0
  • A 0 at the very start of a longer array
  • A 0 at the last index, which does not matter
  • A wall of zeros that some earlier long jump clears
  • Jump lengths far larger than the array

Hints

Hint 1

nums[i] is the maximum jump, so from i you can land on any index from i + 1 to i + nums[i].

Hint 2

If index j is reachable, every index before j is reachable too. So the reachable set is always a prefix.

Hint 3

Track only the furthest index you can reach so far. When does the scan get stuck?

FAQ

What is the best time complexity for Jump Game?

Optimal (greedy furthest reach) runs in O(n) time and O(1) extra space. One pass over the array.

Which pattern does Jump Game use?

It is a arrays & hashing problem that uses the greedy pattern. Other problems with the same pattern: Integer to Roman, Jump Game II, Can Place Flowers.

Is there a brute force solution for Jump Game?

Yes. Brute force (DP over reachable indices) takes O(n²) time and O(n) space. Mark index 0 as reachable.

Which edge cases should I test for Jump Game?

A single element, even if it is 0; A 0 at the very start of a longer array; A 0 at the last index, which does not matter; A wall of zeros that some earlier long jump clears; Jump lengths far larger than the array.