Jump Game

Minimum Jumps

Track the current range you can reach and the farthest you can reach from it. When you exhaust the current range, you must jump — increment the count and set your new range to the farthest. Greedy choice: always stretch as far as possible.

O(n)

O(1)

How It Works

Jump Game II minimizes the number of jumps to reach the end. Treat the scan as implicit BFS over levels: currentEnd marks the boundary of what the current number of jumps covers, while farthest accumulates the best reach from any index inside that window. When the scan hits currentEnd, one more jump is inevitable — increment the count and extend the window to farthest. You never commit to a specific landing index, only to the best possible reach of the next level.

Each index is visited once, so the algorithm is O(n) time and O(1) space, improving on the O(n^2) DP that relaxes every predecessor pair. It is exactly BFS on the jump graph with levels compressed into two integers, which is why the jump count it produces is provably minimal.

Step-by-Step Visualization

Min jumps to reach end

curEnd0

farthest2

1/3

Code

Java

static int jump(int[] nums) {
  int jumps = 0, curEnd = 0, farthest = 0;

  for (int i = 0; i < nums.length - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);
    if (i == curEnd) {
      jumps++;
      curEnd = farthest;
    }
  }
  return jumps;
}
// jump(new int[]{2,3,1,1,4}) → 2

Tips & Gotchas

1Track current range end and farthest reachable

2When you reach range end, you must jump (increment count)

3Update range end to farthest at each jump

Practice Problems

1Jump Game II
2Video Stitching
3Minimum Number of Taps to Open to Water a Garden
4Jump Game VI

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

How is this different from the reachability version of Jump Game?

Reachability needs only the single frontier variable and answers yes/no. Minimizing jumps additionally tracks where the current jump's coverage ends, because that boundary is what forces the jump counter to advance. Two variables instead of one, but still a single linear pass.

Why does the loop typically stop at the second-to-last index?

Reaching the last index requires no further jumps, so processing it can trigger a spurious extra increment when currentEnd lands exactly on it. Iterating i from 0 to n-2 sidesteps that off-by-one entirely.

How do interval problems like Video Stitching reuse this idea?

Each clip [start, end] is an allowed 'jump' covering a range, and choosing minimum clips to cover [0, T] is the same level-by-level extension: among clips starting within the current covered prefix, greedily take the one reaching farthest. The BFS-layer argument carries over unchanged.