Jump Game

Problem Description

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

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

Examples

Constraints

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

Shifting the Goalpost Backward

A naive recursive/backtracking solution tries all jump sizes from each index, which runs in O(2^n) time. Dynamic programming reduces this to O(n²) by caching reachability states.

To optimize to O(n) time, we can use a greedy approach. Instead of checking if we can travel from start to end, we look at the problem in reverse: we check if we can travel from the end back to the start.

Initialize a goal variable to the last index of the array (n - 1). We iterate backward from n - 2 down to 0:

• If we can jump from our current index i to or past the goal (i.e., i + nums[i] >= goal), it means index i is a valid stepping stone.
• We shift our goal to i, making i our new target.
• At the end of the loop, if goal == 0, it means we have successfully traced a path back to the starting index, and we return true.

Solution 1: Greedy Goalpost Shifting (Optimal)

Scan the array backward, updating the goalpost index whenever a cell can reach it.

class Solution {
    public boolean canJump(int[] nums) {
        int goal = nums.length - 1;

        // iterate backward from second to last node
        for (int i = nums.length - 2; i >= 0; i--) {
            // check if current node can reach the active goal
            if (i + nums[i] >= goal) {
                goal = i; // shift goalpost backward
            }
        }
        return goal == 0;
    }
}

class Solution:
    def canJump(self, nums: list[int]) -> bool:
        goal = len(nums) - 1

        # iterate backward from second to last node
        for i in range(len(nums) - 2, -1, -1):
            # check if current node can reach the active goal
            if i + nums[i] >= goal:
                goal = i  # shift goalpost backward

        return goal == 0

#include <vector>

class Solution {
public:
    bool canJump(std::vector<int>& nums) {
        int goal = nums.size() - 1;

        // iterate backward from second to last node
        for (int i = (int)nums.size() - 2; i >= 0; i--) {
            // check if current node can reach the active goal
            if (i + nums[i] >= goal) {
                goal = i; // shift goalpost backward
            }
        }
        return goal == 0;
    }
};

Complexity Analysis:

• Time Complexity: O(n) where n is the length of array nums. We scan the array once.
• Space Complexity: O(1) auxiliary space.

Where it breaks: Nothing breaks for standard input. If nums.length == 1, the loop does not run, and goal is already initialized to 0, correctly returning true.

Common Mistakes

• Starting the loop at nums.length - 1. The last node is already the initial goal. Starting the loop there is redundant.
• Using an O(n²) DP array when O(1) space is possible. Tabulation is acceptable, but the greedy O(1) space solution is the standard expected by interviewers.
• Off-by-one errors in loop termination. The backward loop must run all the way down to index 0, inclusive, to verify reachability from the start.

Frequently Asked Questions

Can we solve this using a forward-scanning greedy approach? Yes. You can scan forward, tracking the maximum reachable index maxReach = max(maxReach, i + nums[i]). At each step, if i > maxReach, it means you have stepped into an unreachable region, and you return false. If maxReach >= n - 1, return true.

What happens if the array has many zeros? If the array has zeros (e.g. [3, 2, 1, 0, 4]), the goalpost will not shift past the zero because i + nums[i] >= goal evaluates to false, correctly returning false at the end.

What does this problem test in interviews? It tests your ability to simplify recursive states by reversing the search perspective and applying greedy optimizations.

← All Problems