A complete visual walkthrough of the greedy BFS approach — from intuition to a clean O(n) solution.
You are given a 0-indexed array of integers nums of length n. You are initially positioned at index 0.
Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at index i, you can jump to any index (i + j) where:
0 <= j <= nums[i] andi + j < nReturn the minimum number of jumps to reach index n - 1. The test cases are generated such that you can reach index n - 1.
Example 1:
Input: nums = [2,3,1,1,4] Output: 2 Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: nums = [2,3,0,1,4] Output: 2
Constraints:
1 <= nums.length <= 1040 <= nums[i] <= 1000nums[n - 1].The straightforward approach treats this as a shortest path problem. From each index, you can jump to indices [i+1, i+nums[i]]. Use BFS to find the minimum jumps to reach the end.
For [2, 3, 1, 1, 4], the BFS explores level by level:
This works but BFS with a queue uses O(n) space and has overhead from queue operations.
The BFS levels are contiguous ranges! Because we can jump to any index from i+1 to i+nums[i], each BFS level is a contiguous subarray. We don't need a queue at all — just track the range boundaries.
Instead of maintaining a queue, we track two boundaries: curEnd (the farthest index reachable in the current number of jumps) and farthest (the farthest index reachable from any position in the current level).
As we scan left to right, we update farthest = max(farthest, i + nums[i]). When i reaches curEnd, we've exhausted the current level — increment jumps and set curEnd = farthest.
Why greedy works here: At each BFS level, we want to reach as far as possible. Among all positions reachable in k jumps, the best next jump is the one that maximizes the new farthest point. Since we scan all positions in the level, we naturally find this maximum.
Let's trace through [2, 3, 1, 1, 4] showing how the three variables evolve.
i < nums.length - 1 ensures we don't process it.class Solution { public int jump(int[] nums) { int jumps = 0; // number of jumps taken int curEnd = 0; // end boundary of current BFS level int farthest = 0; // farthest reachable from current level // Don't process the last index — we just need to reach it for (int i = 0; i < nums.length - 1; i++) { // Update the farthest we can reach farthest = Math.max(farthest, i + nums[i]); // Reached the end of current level? if (i == curEnd) { jumps++; // take a jump curEnd = farthest; // expand to next level } } return jumps; } }
func jump(nums []int) int { jumps := 0 // number of jumps taken curEnd := 0 // end boundary of current BFS level farthest := 0 // farthest reachable from current level // Don't process the last index — we just need to reach it for i := 0; i < len(nums)-1; i++ { // Update the farthest we can reach if i+nums[i] > farthest { farthest = i + nums[i] } // Reached the end of current level? if i == curEnd { jumps++ // take a jump curEnd = farthest // expand to next level } } return jumps }
def jump(nums: list[int]) -> int: jumps = 0 # number of jumps taken cur_end = 0 # end boundary of current BFS level farthest = 0 # farthest reachable from current level # Don't process the last index — we just need to reach it for i in range(len(nums) - 1): # Update the farthest we can reach farthest = max(farthest, i + nums[i]) # Reached the end of current level? if i == cur_end: jumps += 1 # take a jump cur_end = farthest # expand to next level return jumps
impl Solution { pub fn jump(nums: Vec<i32>) -> i32 { let mut jumps = 0; // number of jumps taken let mut cur_end = 0; // end boundary of current BFS level let mut farthest = 0; // farthest reachable from current level // Don't process the last index — we just need to reach it for i in 0..nums.len() - 1 { // Update the farthest we can reach farthest = farthest.max(i + nums[i] as usize); // Reached the end of current level? if i == cur_end { jumps += 1; // take a jump cur_end = farthest; // expand to next level } } jumps } }
function jump(nums: number[]): number { let jumps = 0; // number of jumps taken let curEnd = 0; // end boundary of current BFS level let farthest = 0; // farthest reachable from current level // Don't process the last index — we just need to reach it for (let i = 0; i < nums.length - 1; i++) { // Update the farthest we can reach farthest = Math.max(farthest, i + nums[i]); // Reached the end of current level? if (i === curEnd) { jumps++; // take a jump curEnd = farthest; // expand to next level } } return jumps; }
Enter an array and watch the greedy BFS scan through, tracking jump levels and boundaries.
We scan the array exactly once, doing O(1) work per index. No extra data structures -- just three integer variables (jumps, curEnd, farthest). This is optimal since we must read each element at least once.
From each index, recursively try every reachable next index. Each position can branch into up to n children, and without memoization the recursion tree grows exponentially. Stack depth is at most n.
BFS explores indices level by level using a queue. Each index is dequeued once, but expanding it may enqueue up to n neighbors in the worst case (e.g., [n,n,n,...]). The queue stores at most n entries, giving O(n) space.
A single left-to-right pass tracks two boundaries (curEnd, farthest) using O(1) work per index. Because BFS levels form contiguous ranges, no queue is needed -- just three integer variables replace the entire data structure.
Greedy works because we always extend to the farthest reachable position at each "level." BFS levels form contiguous ranges, so we replace the queue with two pointers. This pattern appears in many "minimum steps" problems -- whenever levels are contiguous, greedy beats BFS.
Review these before coding to avoid predictable interview regressions.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Locally optimal choices may fail globally.
Usually fails on: Counterexamples appear on crafted input orderings.
Fix: Verify with exchange argument or monotonic objective before committing.