A complete visual walkthrough of the greedy BFS approach — from intuition to a clean O(n) solution.
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; } }
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. This is optimal since we must read each element at least once.
From O(n^2) BFS/DP to O(n) greedy. The key insight is that BFS levels form contiguous ranges, letting us replace the queue with two pointers. This pattern appears in many "minimum steps" problems — whenever levels are contiguous, greedy beats BFS.