Topics › Greedy Algorithms › Medium/Hard

Jump Game - I

Easy TUF ID 542 A2ZBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an array nums and you start at index 0. From index i you may jump forward by any number of steps from 1 up to nums[i] (a value of 0 means you cannot move from there). Return true if you can reach the last index, otherwise false.

Constraints: 1 ≤ n ≤ 10^4, 0 ≤ nums[i] ≤ 10^5. The largest reach i + nums[i] is about 1.1 × 10^5, comfortably inside an int.

Example 1

nums = [2, 3, 1, 1, 4]
answer = true       // jump 1 step to index 1, then 3 steps to index 4

Example 2

nums = [3, 2, 1, 0, 4]
answer = false      // every route lands on index 3, whose value 0 lets you go nowhere

Example 3

nums = [2, 0, 0]
answer = true       // jump 2 steps from index 0 straight past the zero at index 1

Approach 1: Brute force, try every jump

Intuition. From index i we can land on any of i + 1, ..., i + nums[i]. The last index is reachable from i if it is reachable from at least one of those. That is a direct recursive definition, with the base case “we are already at (or past) the last index”.

Algorithm.

1. canReach(i): if i ≥ n - 1, return true.
2. For step from 1 to nums[i], if canReach(i + step) is true, return true.
3. Return false.

static boolean bruteForce(int[] nums) {
    return canReach(nums, 0);
}

static boolean canReach(int[] nums, int i) {
    if (i >= nums.length - 1) return true;
    for (int step = 1; step <= nums[i]; step++) {
        if (canReach(nums, i + step)) return true;
    }
    return false;
}

Complexity. Time exponential in the worst case: the same index is re-explored once for every distinct route that reaches it, and the number of routes can grow like 2^n. Space O(n) for the recursion depth.

You can see the waste on Example 2. Index 3 is reached by the routes 0 -> 3, 0 -> 1 -> 3, 0 -> 2 -> 3 and 0 -> 1 -> 2 -> 3, and each route asks again whether index 3 can reach the end, getting the same “no” every time. On a long array full of large values that never reaches the end, the number of such repeated questions explodes.

Approach 2: Better, dynamic programming from the right

Intuition. The recursion asks the same question, “can index j reach the end?”, over and over. Answer it once per index. Work from right to left so that, when we look at index i, every index to its right has already been decided. Call an index good if it can reach the end; index i is good when any index in (i, i + nums[i]] is good.

Algorithm.

1. good[n - 1] = true.
2. For i from n - 2 down to 0, scan j from i + 1 to min(n - 1, i + nums[i]); if some good[j] is true, mark good[i] true and stop scanning.
3. Return good[0].

static boolean better(int[] nums) {
    int n = nums.length;
    boolean[] good = new boolean[n];
    good[n - 1] = true;
    for (int i = n - 2; i >= 0; i--) {
        int far = Math.min(n - 1, i + nums[i]);
        for (int j = i + 1; j <= far; j++) {
            if (good[j]) {
                good[i] = true;
                break;
            }
        }
    }
    return good[0];
}

Complexity. Time O(n^2) in the worst case, since each index may scan up to n positions to its right. Space O(n) for the table.

Approach 3: Optimal, greedy farthest reach

Intuition. The set of reachable indices always forms a prefix of the array: [0, maxReach]. Why? If you can reach some index j by a jump from i, you could also have jumped a shorter distance from i and landed on any index between i and j, because jumps are “up to” nums[i]. So there are no holes, and one number, the farthest reachable index, describes everything.

Scan left to right. If the current index i is within maxReach, it is reachable, so extend maxReach with i + nums[i]. If i is beyond maxReach, nothing could ever land on it, and nothing after it is reachable either, so the answer is false. As soon as maxReach covers the last index we can stop with true.

Algorithm.

1. maxReach = 0.
2. For each i from 0 to n - 1:
   • If i > maxReach, return false.
   • maxReach = max(maxReach, i + nums[i]).
   • If maxReach ≥ n - 1, return true.
3. Return true (only reached for an empty array, which the constraints exclude).

static boolean optimal(int[] nums) {
    int maxReach = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > maxReach) return false;              // index i is unreachable, so is everything after it
        maxReach = Math.max(maxReach, i + nums[i]);
        if (maxReach >= nums.length - 1) return true;
    }
    return true;
}

Dry run on nums = [3, 2, 1, 0, 4]:

Every index up to 3 reaches no farther than 3, so index 4 is unreachable.

Complexity. Time O(n): one pass. Space O(1).

Compared with Approach 2, the greedy replaces a whole table of booleans with a single boundary. Because the reachable indices form a prefix, that boundary is all the information there is.

Edge cases and pitfalls

• Single element. [0] is already at the last index, so the answer is true even though no jump is possible. The maxReach ≥ n - 1 check fires at i = 0.
• Zero at the start. [0, 1] cannot move at all, so the answer is false.
• Zeros are not always fatal. [2, 0, 0] jumps straight over the first zero to the last index. Only a zero that every route must stop on is a problem, which is exactly what i > maxReach detects.
• Overflow. i + nums[i] fits in an int under these constraints. If values could approach Integer.MAX_VALUE, compute the reach in long or cap it at n - 1.
• Overshooting. Jumping past the last index is never needed but is harmless; the checks use ≥ n - 1, not == n - 1.

Related problems

• Jump Game II asks for the minimum number of jumps, extending this greedy into levels.
• Frog Jump is the cost-minimising version where the frog moves one or two steps.
• Frog jump with K distances lets the frog jump up to k steps, like nums[i] here.