45. Jump Game II

At a Glance

Topic: greedy
Pattern: Greedy (level-wise farthest reach / BFS-like)
Difficulty: Medium
Companies: Google, Amazon, Adobe, Apple, Microsoft
Frequency: High
LeetCode: 45

Problem (one-liner)

Same jumps as Jump Game I: from index index you may jump up to nums[index] steps forward. Return the minimum number of jumps to reach the last index. Assume last index always reachable.

Core Basics

Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

Why brute hurts: name the repeated work or state explosion in one sentence.
Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

“Minimum jumps” / “fewest steps”
Greedy layers: each jump extends the frontier to maxReach for next hop count
Related to BFS on implicit graph

Study Pattern (SDE3+)

0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

BFS — queue positions — O(n) time / O(n) space.
Greedy ends of layers — track current window end and farthest in window — O(n) time / O(1) space. <- pick this in interview.

Optimal Solution

Go

package main

func jump(nums []int) int {
	length := len(nums)
	if length <= 1 {
		return 0
	}
	jumps := 0
	currentWindowEnd := 0
	farthestReach := 0
	for index := 0; index < length-1; index++ {
		candidate := index + nums[index]
		if candidate > farthestReach {
			farthestReach = candidate
		}
		if index == currentWindowEnd {
			jumps++
			currentWindowEnd = farthestReach
		}
	}
	return jumps
}

JavaScript

function jump(nums) {
	const length = nums.length;
	if (length <= 1) return 0;
	let jumps = 0;
	let currentWindowEnd = 0;
	let farthestReach = 0;
	for (let index = 0; index < length - 1; index++) {
		farthestReach = Math.max(farthestReach, index + nums[index]);
		if (index === currentWindowEnd) {
			jumps++;
			currentWindowEnd = farthestReach;
		}
	}
	return jumps;
}

Walkthrough

nums = [2,3,1,1,4]

Window end starts 0. After index 0, farthest 2. Increment jump, window end 2.
Iterate indices until 2: best reach 4. Jump again, window end 4 ≥ last.

Invariant: when index reaches current layer boundary, increment jumps and set next boundary to best reach seen in this layer.

Edge Cases

Length 1 → 0 jumps
Large reachable jumps early → few jumps

Pitfalls

Off-by-one when iterating length-1
Confusing with Jump Game I reachability only

Variants

Weighted edges → Dijkstra.

Mind-Map Tags

#greedy #minimum-jumps #layered-bfs #medium