Greedy crash course ↗ · 82

45. Jump Game II

Given an array where nums[i] is the max jump length from index i, find the minimum number of jumps to reach the last index. The greedy insight: treat each jump as a BFS level — track the farthest you can reach and count a new jump whenever you exhaust the current level.

● MediumGreedyBFS by LevelsInterval / ReachTypeScript

PROBLEM What we're solving

You're given nums = [2,3,1,1,4]. From index 0 you can jump up to 2 steps (land at index 1 or 2). Find the fewest jumps to reach the last index (4). The answer is 2: jump from index 0 to 1 (value 3), then jump from 1 to 4. The problem guarantees you can always reach the end.

KEY IDEA Jumps are BFS levels — count level transitions

Insight → Think of each jump as expanding a frontier, exactly like BFS levels. All positions reachable in exactly k jumps form one level. Scan left to right: maintain farthest (max index reachable from any position seen so far) and currentEnd (end of the current level). When i hits currentEnd, you must jump — increment the counter and advance currentEnd = farthest. No queue, no visited set — just two integers.

RECIPE Scan once, jump at each level boundary

  • 0 · Initialise. jumps = 0, currentEnd = 0, farthest = 0. These represent: how many jumps taken, the end of the current BFS level, and the best reach seen in this level.
  • 1 · Scan i = 0 … n−2 (stop before last). For each index, update farthest = max(farthest, i + nums[i]). We stop before the last index because standing there already means we're done — no extra jump needed.
  • 2 · Jump when i hits the boundary. When i === currentEndwe've exhausted everything reachable on the current level. Increment jumps and set currentEnd = farthest to open the next level.
  • 3 · Return jumps. After the loop, jumps holds the minimum count.
Classic confusion → the loop runs to n - 2 (exclusive of the last index), not n - 1. When i === n - 1we're already at the destination — counting a jump there would over-count by one. Many implementations fix this with a special-case check; the cleaner approach is simply stopping the loop one index early.

COST Complexity & alternatives

BFS / DP (explicit)
O(n²)
DP: dp[i] = min(dp[j] + 1) for all reachable j — nested loop.
Greedy BFS-by-levels
O(n)
Single pass, O(1) space — two integer trackers.

The greedy approach works because expanding the farthest reach is always optimal: taking a shorter jump now can never help if a longer jump was available at the same cost. This is the hallmark of a locally optimal = globally optimal greedy argument.

Pattern transfer → the same "BFS level boundary" trick appears in Jump Game I (just check if farthest >= n-1), Jump Game III (BFS with a queue — bidirectional), Minimum Number of Taps to Open to Water a Garden(same greedy on intervals), and any "minimum steps to reach end" interval-coverage problem.

RUN IT Greedy BFS-by-levels: track farthest, jump at currentEnd

step 0 / 7
STARTArray: [2, 3, 1, 1, 4]. We scan left to right, tracking farthest (max reach so far) and currentEnd(end of current jump's range). Jump count starts at 0.
1function jump(nums: number[]): number {
2▶  let jumps = 0;
3▶  let currentEnd = 0;   // boundary of the current "level" (BFS frontier)
4▶  let farthest = 0;     // best reach seen within this level
5 
6  for (let i = 0; i < nums.length - 1; i++) {
7    farthest = Math.max(farthest, i + nums[i]);
8 
9    if (i === currentEnd) {   // exhausted current level — must jump
10      jumps++;
11      currentEnd = farthest;  // next level ends at the best reach
12    }
13  }
14  return jumps;
15}
2031121344
State
0
jumps
0
currentEnd
2
farthest
current index icurrentEnd (jump boundary)reachable from current jumpjumps count
slowfast

TYPESCRIPT The solution, annotated

jumpGameII.ts
function jump(nums: number[]): number {
  let jumps = 0;
  let currentEnd = 0;   // boundary of the current "level" (BFS frontier)
  let farthest = 0;     // best reach seen within this level

  for (let i = 0; i < nums.length - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);

    if (i === currentEnd) {   // exhausted current level — must jump
      jumps++;
      currentEnd = farthest;  // next level ends at the best reach
    }
  }
  return jumps;
}

Reading it block by block

Lines 2–4 — initialise three scalars. jumpscounts how many jumps we've committed to. currentEnd marks the rightmost index we can reach with the jumps taken so far (starts at 0— "we haven't jumped yet"). farthesttracks the best reach we've seen while scanning the current level.
Line 6 — loop to n−2. We iterate every index except the last. Processing the last index would trigger a spurious jumps++ when currentEnd reaches it, over-counting by one.
Line 7 — expand farthest. i + nums[i] is the furthest index reachable in a single jump from position i. We greedily keep the maximum across all positions scanned in the current BFS level.
Lines 9–12 — commit a jump at the level boundary. When i equals currentEndwe've exhausted the current frontier — every index reachable in k jumps has been examined. We must use another jump, so we increment jumps and advance currentEnd to farthest, opening the next BFS level.
Line 14 — return. The loop consumed all indices up to n-2; jumps now holds the exact minimum number of jumps to reach the last index.
Complexity → O(n) time — single pass over n - 1 indices; each index is visited exactly once. O(1) space — three integer variables regardless of input size.

INTERVIEWFollow-ups they'll ask

  • "Return the actual jump sequence, not just the count?" Maintain a parent[] array tracking which index you jumped from at each level transition; backtrack from n-1 after the loop.
  • "What if it's not guaranteed you can reach the end (Jump Game I)?" Check farthest >= n-1 after the loop, or detect when currentEnd stops advancing (stuck on a zero).
  • "Minimum jumps with a cost per jump?" Greedy no longer suffices — switch to BFS/Dijkstra where edge weight encodes the cost.
  • "What's the brute-force approach?" DP: dp[i] = min(dp[j] + 1) for all j that can reach i. O(n²) time and O(n) space — correct but too slow for large inputs.
  • "Edge cases?" Single-element array (n=1) returns 0 — already at destination. All-zero array except the first index (value 0 everywhere) is impossible by the problem guarantee, so no need to handle it.

OPTIMAL Greedy

jumpGameII.ts
function jump(nums: number[]): number {
  let jumps = 0;
  let currentEnd = 0;   // boundary of the current "level" (BFS frontier)
  let farthest = 0;     // best reach seen within this level

  for (let i = 0; i < nums.length - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);

    if (i === currentEnd) {   // exhausted current level — must jump
      jumps++;
      currentEnd = farthest;  // next level ends at the best reach
    }
  }
  return jumps;
}
Complexity → O(n) time — single pass over n - 1 indices; each index is visited exactly once. O(1) space — three integer variables regardless of input size.

ALT 1 Brute force — DP of min jumps to reach each index

O(n²) time · O(n) space

Let dp[i] be the fewest jumps to reach index i. From each reachable i, relax every index in its jump range. The answer is dp[n-1].

approach-2.ts
function jump(nums: number[]): number {
  const n = nums.length;
  const dp = new Array<number>(n).fill(Infinity);
  dp[0] = 0;

  for (let i = 0; i < n; i++) {
    if (dp[i] === Infinity) continue;          // unreachable
    const limit = Math.min(i + nums[i], n - 1);
    for (let j = i + 1; j <= limit; j++) {
      dp[j] = Math.min(dp[j], dp[i] + 1);
    }
  }

  return dp[n - 1];
}
Note → Each index relaxes up to O(n) successors, so the table fill is O(n²). The greedy BFS-by-levels insight — the farthest reach within a level is always the best next frontier — replaces the inner loop with a single O(n) sweep.

MNEMONIC The one-liner

"Scan and stretch the frontier; jump whenever i touches the wall."

TRIGGERS When you see ___ → reach for ___

"minimum jumps to reach end"greedy BFS-by-levels (farthest + currentEnd)
"minimum steps to cover an interval"greedy interval-coverage / jump game pattern
each position has a max reachi + nums[i] for local reach, max across level for global
BFS on implicit graph with O(1) spacelevel boundary trick — no queue needed

SKELETON The reusable shape

skeleton.ts
let jumps = 0;
let currentEnd = 0;
let farthest = 0;

for (let i = 0; i < nums.length - 1; i++) {
  farthest = Math.max(farthest, i + nums[i]);

  if (i === currentEnd) {
    jumps++;
    currentEnd = farthest;
  }
}
return jumps;

FLASHCARDS Tap to flip

What do the three variables track?
jumps = jumps committed; currentEnd = rightmost index reachable in current jump budget; farthest = best reach seen while scanning this level.
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 9
QUESTION 01
What is the time complexity of the greedy solution?
QUESTION 02
For nums = [2,3,1,1,4], what is the minimum number of jumps?
QUESTION 03
Why does the loop run while i < nums.length − 1 (stopping before the last index)?
QUESTION 04
After scanning index i, we update farthest = Math.max(farthest, i + nums[i]). What does i + nums[i] represent?
QUESTION 05
What happens to currentEnd after we decide to jump?
QUESTION 06
nums = [1,1,1,1]. How many jumps are taken and how many jumps++ events fire?
QUESTION 07
The DP approach solves Jump Game II in O(n²). What makes the greedy approach strictly better?
QUESTION 08
#45 · Jump Game IIGreedy BFS by levels: track the farthest reachable index within the current jump range and increment the jump counter when the scan reaches the current boundary — minimizing jumps in O(n).Which algorithmic approach does this primarily use?
QUESTION 09
#45 · Jump Game IIGreedy BFS by levels: track the farthest reachable index within the current jump range and increment the jump counter when the scan reaches the current boundary — minimizing jumps in O(n).Which implementation correctly solves it?