Frontend Beauty
ESC

Type to search the knowledge base.

Jump Game

Can you reach the last index — greedy farthest reach, DP alternative, and when zero cells trap you.

intermediate3 min read
  • dsa
  • greedy
  • interview
  • Google
  • Meta

The problem

nums[i] = max jump length from index i. Start at 0. Return true if you can reach the last index.

[2,3,1,1,4] → true
[3,2,1,0,4] → false

Brute / DP

function canJumpDp(nums: number[]): boolean {
  const n = nums.length;
  const ok = new Array<boolean>(n).fill(false);
  ok[0] = true;
  for (let i = 0; i < n; i++) {
    if (!ok[i]) continue;
    for (let j = 1; j <= nums[i] && i + j < n; j++) ok[i + j] = true;
  }
  return ok[n - 1];
}
Time O(n²) worst
Space O(n)

Optimal greedy: farthest reachable

Track far = max index reachable so far. Iterate i from 0 to far. At each i, far = max(far, i + nums[i]). If far >= n-1, true. If loop ends with far < n-1, false.

function canJump(nums: number[]): boolean {
  let far = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > far) return false;
    far = Math.max(far, i + nums[i]);
    if (far >= nums.length - 1) return true;
  }
  return true;
}
Time O(n)
Space O(1)

Walk false case [3,2,1,0,4]

i far after
0 max(0,3)=3
1 max(3,3)=3
2 max(3,3)=3
3 max(3,3)=3
4 > far → false

Edge cases

  • Single element → true
  • nums[0]=0 and n>1 → false
  • Zeros that are still reachable intermediate

Common mistakes

  • Only checking last non-zero
  • BFS without need (correct but heavier)
  • Confusing with Jump Game II (min jumps)

Interview delivery

  1. Reachability not min jumps.
  2. Farthest pointer.
  3. Fail when i > far.
  4. O(n).
  5. Mention II as follow-up.

Mental model

Maintain the frontier of indices you can still stand on. If you ever scan past the frontier, you’re stuck. Updating frontier with i + nums[i] is the greedy reachability step.

DP vs greedy

DP marks all reachable indices explicitly. Greedy only tracks the max frontier — enough for a boolean answer. Jump Game II needs more structure (layers) for min jumps.

Out-loud answer

“Track farthest reachable. For each i ≤ far, extend far. If i > far return false. If far covers last index return true. O(n)/O(1). Zeros only kill you if you can’t jump over them.”

Complexity table

Approach Time Space
DFS/BFS visited O(n²) edges worst O(n)
DP reachable flags O(n²) O(n)
Greedy farthest O(n) O(1)

Interview delivery

  1. Boolean reachability.
  2. Farthest pointer.
  3. Fail when i>far.
  4. Trace zero trap.
  5. Point to Jump Game II for min jumps.

Further reading