Jump Game II

PracticeNeetCode ↗LeetCode ↗

Given an integer array nums where each element is the maximum jump length from that position, return the minimum number of jumps needed to reach the last index. It's guaranteed the last index is always reachable.

Example

Key Pointers

• Think in terms of jump "boundaries" rather than individual jumps — within the range reachable by the current jump, find the farthest point reachable by one more jump.
• A new jump only gets counted once you've exhausted the current jump's range (reached its boundary).
• This behaves like a level-by-level BFS expansion, but done greedily in a single pass without an explicit queue.

Step-by-Step Analysis

1. Initialize jumps = 0, curEnd = 0 (boundary of the current jump), farthest = 0.
2. For each index i from 0 to len(nums) - 2: update farthest = max(farthest, i + nums[i]).
3. If i == curEnd (the current jump's range is exhausted), increment jumps and set curEnd = farthest.
4. Return jumps once the loop completes.

Complexity

Time: O(n) — Space: O(1)

Code

def jump(nums: list[int]) -> int:
    jumps = 0
    curEnd = 0
    farthest = 0

    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == curEnd:
            jumps += 1
            curEnd = farthest

    return jumps

Code Explanation

How the solution above works, piece by piece.

1. Treat reachable indices as levels, like BFS: all indices reachable with the same number of jumps form one range.
2. farthest tracks the furthest index reachable from anything in the current range.
3. When i reaches curEnd (the end of the current range), one more jump is required; the next range ends at farthest.
4. The loop stops before the last index: being at the last index needs no further jump.
5. O(n) time, O(1) space.

Visual Walkthrough

Running it on nums = [2, 3, 1, 1, 4]:

Video Explanation

NeetCode — Greedy, LeetCode 45