LeetCode 55 · Medium · Greedy

Jump Game

You stand on index 0 of nums, and from index i you may jump forward up to nums[i] steps. Return true if you can land on the last index.

O(n)time
O(1)space
goal postslides left

comma-separated integers · 1–12 values · each 0 to 9

public boolean canJump(int[] nums) { int goal = nums.length - 1; for (int i = nums.length - 1; i >= 0; i--) { if (i + nums[i] >= goal) { // i can hop onto the goal goal = i; } } return goal == 0;}
i
—
nums[i]
—
i + nums[i]
—
goal
—

Why it works

  1. Brute force tries every jump length from every index, recursively: exponential without memo, O(n²) as a DP table of "can index i reach the end?".
  2. Only the leftmost good index matters. Walk from the end. goal is the leftmost index known to reach the last one. Index i is good if it can hop onto goal: anything past goal that i could reach is reachable from goal anyway.
  3. One sweep, one number: each index is checked once against goal, so O(n) time and O(1) space.
  4. Pitfall: use >=, not >. A jump that lands exactly on goal counts, and a 0 sitting on the last index never matters, because you only need to land there.
  5. Forward version: track the farthest reachable index while scanning left to right, and fail the moment i passes it. Jump Game II (45) extends that window idea to count the jumps.