DSA Tracker

Visualize

Jump Game

Greedy farthest-reach sweep

time O(n)space O(1)

Instead of exploring every jump combination, the greedy sweep keeps ONE number: reach, the farthest index any sequence of jumps can touch so far. Scan left to right — if the current index is within reach, its jump may extend the frontier; if the index ever passes reach, no jump could have carried you there and the answer is false.

Details

Animated on: Jump Game: in [3, 1, 0, 2, 5, 1, 1] each value is the max jump length from that cell — can you reach the last index (6)?

Problem:Jump GameMedium

Pattern:Greedy Scheduling and Sorting

Greedy farthest-reach sweep

step 1 / 10

3
[0]
1
[1]
0
[2]
2
[3]
5
[4]
1
[5]
1
[6]

Each value is the FARTHEST you may hop forward from that cell. Greedy tracks a single frontier: reach = 0, the farthest index provably reachable. Goal: touch index 6.

  • i=0· arr[0] = 3
  • reach=0· arr[0] = 3
Pseudocode
1FUNCTION canJump(nums):
2  reach = 0
3  FOR i from 0 to n-1:
4    IF i > reach: RETURN false   (stranded)
5    reach = the larger of reach and i + nums[i]
6    IF reach >= n-1: RETURN true
7  RETURN true

← / → step · space play · Home restart

Every step in words

Show all 10 steps
  1. Each value is the FARTHEST you may hop forward from that cell. Greedy tracks a single frontier: reach = 0, the farthest index provably reachable. Goal: touch index 6.
  2. Stuck test first: i = 0 ≤ reach = 0, so we are standing on reachable ground (the start). If i ever exceeds reach, no jump could have carried us here — that's the only way to lose.
  3. From index 0 the value 3 lets us land on index 1, 2 or 3 — reach = max(0, 0+3) = 3. Every cell up to the reach marker is now provably reachable; we never track HOW, only how far.
  4. i = 1 sits under reach = 3. Its offer: 1+1 = 2, worse than the frontier we already own, so reach stays 3. Greedy keeps only the best frontier — weaker offers change nothing.
  5. The 0 at i = 2: land here and stop, and you're trapped (2+0 = 2). But reach = 3 was earned back at index 0 — the plan can hop straight OVER this cell. A zero inside the frontier is harmless.
  6. i = 3 equals reach = 3 — the exact edge of the frontier, reachable by the full 3-jump from index 0. One index further with no update and we'd be stranded. Not stuck yet.
  7. Index 3 offers 3+2 = 5 > 3 — the frontier extends: reach = 5. This is why the sweep visits EVERY reachable cell: any one of them might be the launchpad that pushes reach further.
  8. Goal test: reach = 5 is still short of the last index 6 — not done. Keep scanning; i = 4 is next and sits safely inside the frontier.
  9. i = 4 ≤ 5: reachable — and its jump is huge. reach = max(5, 4+5) = 9, sailing past the end of the array (marker parked on the last cell). The frontier now covers everything.
  10. reach = 9 ≥ 6: return true. One concrete route: 0 → 3 → 4 → 6 (jumps of 3, 1, 2 — each within its cell's limit); the grey cells never need to be landed on. One integer and one pass replaced the exponential tree of jump choices.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Jump Game in the editorAll Greedy problemsBack to roadmap