Jump Game — Greedy Max-Reach Beats DP

Jump Game looks like a dynamic programming problem at first glance — and you can solve it that way. But there is a beautifully simple greedy that runs in O(n) time and O(1) space.

The Problem

You are given an integer array nums. You start at index 0. Each element nums[i] is the maximum jump length from that position. Return true if you can reach the last index, otherwise false.

Example: [2,3,1,1,4] returns true. [3,2,1,0,4] returns false because index 3 has a zero and we cannot get past it.

Intuition

The DP defines reachable[i] as true if index i is reachable from index 0. From every reachable i, mark i+1 through i + nums[i] reachable. Correct but O(n^2) in the worst case.

You do not need to track which specific indices are reachable. You only need the furthest index reachable so far. As you scan left to right, you keep updating that frontier. The moment you visit an index past the frontier, you are stuck. Why is this safe? The set of reachable indices is always a prefix [0, max_reach]. That prefix shape is exactly what makes greedy collapse into the right answer.

Explanation with Example

Take nums = [2,3,1,1,4].

• i=0: max_reach = max(0, 0+2) = 2.
• i=1: 1 <= 2, max_reach = max(2, 1+3) = 4. Already covers the end (index 4). Return True.

index       0   1   2   3   4
nums        2   3   1   1   4

i=0  reach= 2   |==>|
i=1  reach= 4   |==========>|
i=2  reach= 4   |==========>|
i=3  reach= 4   |==========>|
i=4  reach >= n-1, return True

For [3,2,1,0,4]: i=0 max_reach=3. i=1 max_reach=3. i=2 max_reach=3. i=3 max_reach=3. i=4: 4 > 3, return False.

Code

def can_jump(nums):
    max_reach = 0
    for i, step in enumerate(nums):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + step)
        if max_reach >= len(nums) - 1:
            return True
    return True

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

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxReach = 0;
        for (int i = 0; i < (int)nums.size(); ++i) {
            if (i > maxReach) return false;
            maxReach = max(maxReach, i + nums[i]);
            if (maxReach >= (int)nums.size() - 1) return true;
        }
        return true;
    }
};

O(n) time, O(1) space.

Edge Cases

• Single element [0]: returns true — you start at the last index.
• First element is zero with length > 1: returns false.
• Array of all zeros except the start: depends on whether the first jump can clear them.
• Very large jump at index 0: short-circuits immediately.

Complexity Analysis

• Time: O(n). One linear scan.
• Space: O(1). A single integer.

Why is greedy safe here?

If index i is reachable, then every index j < i from which we could have jumped to i is also reachable. So tracking only the maximum reach loses no information — it is a complete summary of reachability.

Variants

Jump Game II asks for the minimum number of jumps. Track the current jump’s boundary and the farthest you could reach with one more jump. When you walk off the current boundary, commit to a jump. Same O(n) shape.

Jump Game III turns it into a graph traversal — BFS/DFS, not greedy. A useful contrast for understanding when greedy applies.

Interview talking points

• Start by stating the brute force or DP solution to anchor the conversation.
• Pivot to greedy and explain the invariant: “the reachable set is always a prefix.”
• Be explicit about complexity: O(n) time, O(1) space.
• Mention Jump Game II as a natural follow-up.

The bigger lesson: when a DP solution’s state can be summarized by a single number, there is often a greedy hiding behind it. Train your eye to look for that compression — it is how O(n^2) problems become O(n).