Skip to main content
Jump Game

Can You Reach the End?

Walk through the array, tracking the farthest index you can reach. At each position, update farthest = max(farthest, i + nums[i]). If at any point i > farthest, you're stuck. If farthest ≥ last index, you can make it.

O(n)
·
O(1)

How It Works

Jump Game asks whether you can reach the last index when nums[i] is the maximum jump length from position i. Sweep left to right maintaining farthest, the highest index reachable so far. At each index i, first check i <= farthest — if not, you are stranded and the answer is false — then update farthest = max(farthest, i + nums[i]). If farthest ever reaches the last index, return true.

The insight making greedy valid is that reachability is contiguous: if index r is reachable, every index below r is too, so a single frontier number summarizes the entire reachable set. That collapses what looks like a BFS or DP over jump choices into one O(n) pass with O(1) space, versus O(n^2) for the naive DP that checks every predecessor.

Step-by-Step Visualization

Can you reach the last index?
2
0
3
1
1
2
1
3
4
4
Farthest0+2 = 2
1/3

Code

Java
static boolean canJump(int[] nums) {
  int farthest = 0;

  for (int i = 0; i < nums.length; i++) {
    if (i > farthest) return false;
    farthest = Math.max(farthest, i + nums[i]);
  }
  return true;
}
// canJump(new int[]{2,3,1,1,4}) → true

Tips & Gotchas

1Track farthest reachable index as you scan
2If current index > farthest, you're stuck
3Update farthest = max(farthest, i + nums[i])

Practice Problems

  • 1Jump Game
  • 2Jump Game III
  • 3Jump Game VII
  • 4Frog Jump

About the Jump Game Pattern

From each position, you can jump up to nums[i] steps forward. Track the farthest position reachable. If you can always extend your reach, you can reach the end.

Key insight

Greedy is NOT 'try the obvious thing'. It works only when local optimality guarantees global optimality. Sort first (by end time, deadline, ratio), then pick greedily. If greedy fails, try DP.

Common Greedy Interview Problems

  • Jump Game
  • Activity Selection
  • Meeting Rooms II
  • Gas Station
  • Candy
  • Task Scheduler
  • Partition Labels

Frequently Asked Questions

Why is DP unnecessary when jumps look like a graph problem?

Because you may jump any distance up to nums[i], the set of reachable indices is always a prefix — there are no holes. One number, the farthest frontier, encodes the whole state, so tracking per-index reachability adds cost without adding information.

When does the greedy frontier stop working for jump variants?

Whenever jumps are exact rather than up-to (Jump Game III jumps exactly arr[i] either direction) or carry extra state (Frog Jump's next jump depends on the last jump size). Broken contiguity means you need BFS, DFS, or DP over richer states.

What edge cases commonly break implementations?

A single-element array is trivially reachable even if its value is 0, and zeros elsewhere only matter when the frontier cannot pass them. Checking i <= farthest before updating — not after — is what correctly detects being stuck at a zero.