Jump Game

Approach Summary

Track max reachable index. If current index exceeds max reachable, return false. Update max at each step.

Full Solution & Approach

You never need to decide which jump to take — only track how far you could have reached. Maintain max_reach, the farthest index reachable so far, initialized to nums[0]. Iterate through the array; if the current index is beyond max_reach, an earlier position could not carry you here — return false. Otherwise update max_reach = max(max_reach, i + nums[i]). If max_reach reaches or exceeds the last index at any point, you can finish — though the loop completes naturally anyway. The greedy is correct because the reachability of a position depends only on whether some earlier reachable position could jump to it, and tracking the maximum reach subsumes every individual jump choice. This is a strictly simpler problem than Jump Game II — no jump counting is needed.

A single pass with constant work per element — O(n) time. One scalar — O(1) space.

Solution Code

Solution

def can_jump(nums: list[int]) -> bool:
    max_reach = 0
    for i, n in enumerate(nums):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + n)
    return True

function canJump(nums) {
  let maxReach = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > maxReach) return false;
    maxReach = Math.max(maxReach, i + nums[i]);
  }
  return true;
}

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]);
    }
    return true;
}

bool canJump(const 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]);
    }
    return true;
}

Edge Cases to Watch

Single element — already at the end, true
All zeros after the first — false unless the first jump clears them
Large first jump — max_reach jumps far immediately
Zeros mid-array that are jumped over — handled by max_reach

How to Recognize This Pattern

Can you reach the end?
Greedy max reach

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)