45. Jump Game II (Medium)

Problem

Given an integer array nums where each nums[i] gives the max jump length from index i, return the minimum number of jumps to reach the last index. You can assume the last index is always reachable.

Example

• nums = [2, 3, 1, 1, 4] → 2
• nums = [2, 3, 0, 1, 4] → 2

LeetCode 45 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Naive starting point: try every jump

The most direct version is recursive: from index i, try every legal next jump and keep the path that uses the fewest jumps.

def jump(nums):
    n = len(nums)

    def dfs(i):
        if i >= n - 1:
            return 0

        best = float("inf")
        for step in range(1, nums[i] + 1):
            best = min(best, 1 + dfs(i + step))

        return best

    return dfs(0)

For nums = [2, 3, 1, 1, 4], index 0 can jump to index 1 or index 2.

dfs(0) = 1 + min(dfs(1), dfs(2))

From index 1, one more jump can reach index 4, so dfs(1) = 1. From index 2, the path is 2 -> 3 -> 4, so dfs(2) = 2.

dfs(0) = 1 + min(1, 2) = 2

This captures the problem correctly, but it repeats work. The same index can be reached through many previous choices, so the recursion tree grows fast. Memoization turns it into a DP. The optimal greedy solution goes one step further: it notices that all indices reachable with the same jump count form a range.

Approach 1: DP, min jumps to reach each index

dp[i] = min jumps to reach i. dp[i] = min(dp[j] + 1) over j from which i is reachable.

Python

def jump(nums):
    n = len(nums)                           # L1: O(1)
    INF = float('inf')
    dp = [INF] * n                          # L2: O(n)
    dp[0] = 0                               # L3: O(1)
    for i in range(n):                      # L4: outer loop, n iterations
        if dp[i] == INF:
            continue
        furthest = min(i + nums[i], n - 1)  # L5: O(1)
        for j in range(i + 1, furthest + 1):# L6: inner loop, up to n per i
            dp[j] = min(dp[j], dp[i] + 1)  # L7: O(1)
    return dp[n - 1]

TypeScript

function jump(nums: number[]): number {
    const n = nums.length;                                  // L1: O(1)
    const dp: number[] = new Array(n).fill(Infinity);      // L2: O(n)
    dp[0] = 0;                                             // L3: O(1)
    for (let i = 0; i < n; i++) {                          // L4: outer loop, n iterations
        if (dp[i] === Infinity) continue;
        const furthest = Math.min(i + nums[i], n - 1);     // L5: O(1)
        for (let j = i + 1; j <= furthest; j++) {          // L6: inner loop, up to n per i
            dp[j] = Math.min(dp[j], dp[i] + 1);           // L7: O(1)
        }
    }
    return dp[n - 1];
}

Go

func jump(nums []int) int {
    n := len(nums)                                          // L1: O(1)
    const INF = 1<<62
    dp := make([]int, n)                                    // L2: O(n)
    for i := range dp { dp[i] = INF }
    dp[0] = 0                                               // L3: O(1)
    for i := 0; i < n; i++ {                               // L4: outer loop, n iterations
        if dp[i] == INF { continue }
        furthest := i + nums[i]                             // L5: O(1)
        if furthest > n-1 { furthest = n - 1 }
        for j := i + 1; j <= furthest; j++ {               // L6: inner loop, up to n per i
            if dp[i]+1 < dp[j] { dp[j] = dp[i] + 1 }     // L7: O(1)
        }
    }
    return dp[n-1]
}

Swift

final class Solution {
    func jump(_ nums: [Int]) -> Int {
        var jumps = Array(repeating: Int.max, count: nums.count)
        jumps[0] = 0
        for index in nums.indices {
            if jumps[index] == Int.max { continue }
            let end = min(nums.count - 1, index + nums[index])
            if index < end {
                for next in (index + 1)...end { jumps[next] = min(jumps[next], jumps[index] + 1) }
            }
        }
        return jumps[nums.count - 1]
    }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L2 (init dp)	$O(1)$	n	$O(n)$
L4 (outer loop)	$O(1)$	n	$O(n)$
L6, L7 (inner loop)	$O(1)$	up to n per i	$O(n²)$ ← dominates

L6 is the bottleneck: for each index i we may scan up to nums[i] forward positions. In the worst case (e.g., nums = [n, n, n, ...]) each outer iteration scans nearly the entire remaining array, giving $O(n²)$ total.

Complexity

• Time: $O(n²)$, driven by L6/L7 (the inner scan for reachable positions).
• Space: $O(n)$ for the dp array.

Approach 2: BFS on jump levels

Treat each jump as a BFS level. All positions reachable in k jumps form level k. Return the level that contains the last index.

Python

def jump(nums):
    n = len(nums)                                   # L1: O(1)
    if n <= 1:
        return 0
    visited = [False] * n                           # L2: O(n)
    visited[0] = True
    level = 0                                       # L3: O(1)
    frontier = [0]                                  # L4: O(1)
    while frontier:                                 # L5: outer loop, one per jump level
        level += 1
        next_frontier = []
        for i in frontier:                          # L6: iterate current frontier
            for k in range(1, nums[i] + 1):         # L7: try each reachable step
                j = i + k
                if j >= n - 1:
                    return level
                if not visited[j]:
                    visited[j] = True
                    next_frontier.append(j)         # L8: O(1) amortized
        frontier = next_frontier
    return -1

TypeScript

function jump(nums: number[]): number {
    const n = nums.length;                                  // L1: O(1)
    if (n <= 1) return 0;
    const visited: boolean[] = new Array(n).fill(false);   // L2: O(n)
    visited[0] = true;
    let level = 0;                                         // L3: O(1)
    let frontier: number[] = [0];                          // L4: O(1)
    while (frontier.length > 0) {                          // L5: outer loop, one per jump level
        level++;
        const nextFrontier: number[] = [];
        for (const i of frontier) {                        // L6: iterate current frontier
            for (let k = 1; k <= nums[i]; k++) {           // L7: try each reachable step
                const j = i + k;
                if (j >= n - 1) return level;
                if (!visited[j]) {
                    visited[j] = true;
                    nextFrontier.push(j);                  // L8: O(1) amortized
                }
            }
        }
        frontier = nextFrontier;
    }
    return -1;
}

Go

func jump(nums []int) int {
    n := len(nums)                                          // L1: O(1)
    if n <= 1 { return 0 }
    visited := make([]bool, n)                              // L2: O(n)
    visited[0] = true
    level := 0                                              // L3: O(1)
    frontier := []int{0}                                    // L4: O(1)
    for len(frontier) > 0 {                                 // L5: outer loop, one per jump level
        level++
        var nextFrontier []int
        for _, i := range frontier {                        // L6: iterate current frontier
            for k := 1; k <= nums[i]; k++ {                // L7: try each reachable step
                j := i + k
                if j >= n-1 { return level }
                if !visited[j] {
                    visited[j] = true
                    nextFrontier = append(nextFrontier, j)  // L8: O(1) amortized
                }
            }
        }
        frontier = nextFrontier
    }
    return -1
}

Swift

final class Solution {
    func jump(_ nums: [Int]) -> Int {
        if nums.count == 1 { return 0 }
        var frontier = Set([0]), seen = frontier, jumps = 0
        while !frontier.isEmpty {
            jumps += 1
            var next = Set<Int>()
            for index in frontier {
                let end = min(nums.count - 1, index + nums[index])
                if index < end {
                    for destination in (index + 1)...end {
                        if destination == nums.count - 1 { return jumps }
                        if seen.insert(destination).inserted { next.insert(destination) }
                    }
                }
            }
            frontier = next
        }
        return jumps
    }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L2 (init visited)	$O(1)$	n	$O(n)$
L5 (BFS level loop)	$O(1)$	up to n levels	$O(n)$
L6, L7 (frontier scan)	$O(1)$	up to n² total	$O(n²)$ ← dominates
L8 (append)	$O(1)$ amortized	up to n	$O(n)$

Each node is visited at most once (the visited guard), so total work across all levels is bounded by total edges, which is $O(n²)$ worst case (when each node points to all following nodes).

Complexity

• Time: $O(n²)$ worst case, driven by L6/L7.
• Space: $O(n)$ for visited and frontier arrays.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Greedy with current-end + farthest (optimal)

Track the rightmost index reachable within the current jump (current_end) and the global farthest reachable (farthest). When you cross current_end, you must have jumped once more, so set current_end = farthest.

Python

def jump(nums):
    jumps = 0                                   # L1: O(1)
    current_end = 0                             # L2: O(1)
    farthest = 0                                # L3: O(1)
    for i in range(len(nums) - 1):              # L4: scan every index except the destination
        farthest = max(farthest, i + nums[i])   # L5: O(1) per step
        if i == current_end:                    # L6: O(1) per step
            jumps += 1
            current_end = farthest
    return jumps

TypeScript

function jump(nums: number[]): number {
    let jumps = 0;                                          // L1: O(1)
    let currentEnd = 0;                                    // L2: O(1)
    let farthest = 0;                                      // L3: O(1)
    for (let i = 0; i < nums.length - 1; i++) {            // L4: scan every index except the destination
        farthest = Math.max(farthest, i + nums[i]);        // L5: O(1) per step
        if (i === currentEnd) {                            // L6: O(1) per step
            jumps++;
            currentEnd = farthest;
        }
    }
    return jumps;
}

Go

func jump(nums []int) int {
    jumps := 0                                              // L1: O(1)
    currentEnd := 0                                        // L2: O(1)
    farthest := 0                                          // L3: O(1)
    for i := 0; i < len(nums)-1; i++ {                     // L4: scan every index except the destination
        if i+nums[i] > farthest { farthest = i + nums[i] } // L5: O(1) per step
        if i == currentEnd {                               // L6: O(1) per step
            jumps++
            currentEnd = farthest
        }
    }
    return jumps
}

Swift

final class Solution {
    func jump(_ nums: [Int]) -> Int {
        if nums.count == 1 { return 0 }
        var jumps = 0, currentEnd = 0, farthest = 0
        for index in 0..<(nums.count - 1) {
            farthest = max(farthest, index + nums[index])
            if index == currentEnd { jumps += 1; currentEnd = farthest }
        }
        return jumps
    }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1-L3 (init)	$O(1)$	1	$O(1)$
L4 (loop)	$O(1)$	n-1	$O(n)$ ← dominates
L5 (update farthest)	$O(1)$	n-1	$O(n)$
L6 (commit jump)	$O(1)$	at most n-1	$O(n)$

The scan includes index 0, because the first jump range comes from nums[0]. It stops before the destination, because reaching the last index already ends the trip. Every line executes once per scanned index, with $O(1)$ work per step.

Complexity

• Time: $O(n)$, driven by L4 (single linear scan).
• Space: $O(1)$.

Intuition

This is BFS collapsed into a linear scan: the “frontier” of a BFS level is implicit in the window [prev_end, current_end]. Each time the walking index reaches current_end, we “commit” to another jump and extend to farthest.

Walkthrough

Use nums = [2, 3, 1, 1, 4].

index:  0  1  2  3  4
nums:   2  3  1  1  4

At index 0, nums[0] = 2, so one jump can reach indices 1 and 2.

0 jumps: [0]
1 jump:  [1, 2]

The question becomes: from anywhere in [1, 2], how far can the next jump reach?

from index 1: 1 + nums[1] = 4
from index 2: 2 + nums[2] = 3

The best next boundary is 4, so two jumps can reach the destination.

0 jumps: [0]
1 jump:  [1, 2]
2 jumps: [3, 4]

The algorithm tracks only the right edge of those ranges:

• current_end: the farthest index reachable with the current number of committed jumps.
• farthest: the farthest index reachable with one more jump from anything scanned in the current range.
• jumps: the number of completed range expansions.

When i == current_end, the current range is fully scanned. Spend one jump and move current_end to farthest.

How to recognize this pattern

• Minimum number of jumps: Minimum moves with equal cost points to BFS.
• Forward jump: Edges only move right, so a left-to-right scan can replace a queue.
• Maximum length from each index: Each index opens a range of next positions, not one fixed next state.
• Guaranteed reachable: The solution can focus on the minimum count, not failure cases.
• n <= 10^4: Exponential recursion is out. A quadratic DP is understandable, but the array shape hints that a range-based scan exists.

The recognition leap is that the BFS frontier is contiguous. All positions reachable in one jump form a range. All positions reachable in two jumps form the next range. The greedy scan keeps the best next right edge while walking the current range.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
DP	$O(n²)$	$O(n)$
BFS levels	$O(n²)$ worst	$O(n)$
Greedy with farthest	$O(n)$	$O(1)$

One of the cleanest greedy collapses of a BFS structure.

Test cases

Go

func jump(nums []int) int {
    jumps := 0
    currentEnd := 0
    farthest := 0
    for i := 0; i < len(nums)-1; i++ {
        if i+nums[i] > farthest { farthest = i + nums[i] }
        if i == currentEnd {
            jumps++
            currentEnd = farthest
        }
    }
    return jumps
}

Python

# Quick smoke tests, paste into a REPL or save as test_045.py and run.
# Uses the canonical implementation (Approach 3: greedy).

def jump(nums):
    jumps = 0
    current_end = 0
    farthest = 0
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == current_end:
            jumps += 1
            current_end = farthest
    return jumps

def _run_tests():
    assert jump([2, 3, 1, 1, 4]) == 2
    assert jump([2, 3, 0, 1, 4]) == 2
    assert jump([1]) == 0          # single element, already at end
    assert jump([1, 1, 1, 1]) == 3
    assert jump([5, 4, 3, 2, 1, 0]) == 1  # jump over everything in one step
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function jump(nums: number[]): number {
    let jumps = 0;
    let currentEnd = 0;
    let farthest = 0;
    for (let i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);
        if (i === currentEnd) {
            jumps++;
            currentEnd = farthest;
        }
    }
    return jumps;
}

console.assert(jump([2, 3, 1, 1, 4]) === 2);
console.assert(jump([2, 3, 0, 1, 4]) === 2);
console.assert(jump([1]) === 0);          // single element, already at end
console.assert(jump([1, 1, 1, 1]) === 3);
console.assert(jump([5, 4, 3, 2, 1, 0]) === 1);  // jump over everything in one step
console.log("all tests pass");

Related data structures

• Arrays, scalar running bounds

Related concepts

• Greedy Algorithms, the local choice pattern protected by an invariant about the best reachable future.
• Array Scans, the linear pass habit of carrying just enough state while reading each item once.