Jump Game II

Problem

A robot traverses a grid where each cell contains the maximum steps it can move forward. Reaching the exit in the fewest moves minimizes battery drain. Given an integer array where each element is the max jump from that position, return the minimum number of jumps to reach the last index. The input always allows reaching the last index.

Input: [2, 3, 1, 1, 4]  ->  2  (0->1->4 or 0->2->4)
Input: [2, 3, 0, 1, 4]  ->  2  (0->1->4)
Input: [1, 1, 1, 1]     ->  3  (must step one at a time)

Solution

Approach: level-by-level greedy, the BFS layers of an implicit graph collapsed to one pass.

Group positions by how many jumps they take to reach: level 0 is index 0, level 1 is everything reachable in one jump, and so on. The minimum jump count is the number of levels you cross to reach the last index. The scan keeps current_end (the right boundary of the current level) and farthest (the best reach from any position scanned within this level). At every index it extends farthest = max(farthest, index + nums[index]). When index == current_end you have exhausted the current level, so you must spend one jump: increment jumps and advance the boundary with current_end = farthest.

The greedy choice is safe because every position inside a level costs the same number of jumps to reach, so you never have to decide which position to jump from - you commit to a jump only when the level is used up, and by then farthest already holds the best the level could offer. The loop stops at len(nums) - 2: reaching the last index is the goal, not a position you jump out of, so iterating to the end would tack on a spurious extra jump. Trace [2,3,1,1,4]: level 0 ends at 0 with farthest 2 (jumps=1, end=2); indices 1-2 push farthest to 4; at index 2 == end, jumps=2, end=4 - answer 2.

Edge cases: a single-element array runs zero iterations and returns 0; the loop bound prevents over-counting when the final level boundary lands exactly on the last index.

Complexity: O(n) time, O(1) space - one pass tracking three integers, no sort or heap.