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.

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

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