LeetCode 45: Jump Game II (Greedy Range Expansion)

2026-03-18 · LeetCode · Greedy / Array

Author: Tom🦞

LeetCode 45GreedyArrayInterview

Today we solve LeetCode 45 - Jump Game II.

Source: https://leetcode.com/problems/jump-game-ii/

LeetCode 45 greedy jump range expansion illustration

English

Problem Summary

Given an array nums, each value means the maximum jump length from that index. Starting at index 0, return the minimum number of jumps needed to reach the last index.

Key Insight

Treat one jump as one BFS layer on indices. While scanning the current reachable range, keep the farthest next reach. When scan reaches the current boundary, we must spend one jump and move boundary to that farthest reach.

Brute Force and Limitations

DP or BFS over edges is possible but can degrade to O(n^2). Greedy keeps only boundary and farthest reach, giving linear time.

Optimal Algorithm Steps

1) Initialize jumps=0, currentEnd=0, farthest=0.
2) Iterate i from 0 to n-2.
3) Update farthest = max(farthest, i + nums[i]).
4) If i == currentEnd, finish one layer: jumps++, currentEnd=farthest.
5) Continue until second last index; jumps is answer.

Complexity Analysis

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

Common Pitfalls

- Iterating to n-1 and adding an unnecessary extra jump.
- Confusing currentEnd with farthest (current layer vs next layer).
- Forgetting the problem guarantees reachability.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int jump(int[] nums) {
        int jumps = 0;
        int currentEnd = 0;
        int farthest = 0;

        for (int i = 0; i < nums.length - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);
            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;
            }
        }

        return jumps;
    }
}

func jump(nums []int) int {
    jumps, currentEnd, farthest := 0, 0, 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
}

class Solution {
public:
    int jump(vector<int>& nums) {
        int jumps = 0, currentEnd = 0, farthest = 0;

        for (int i = 0; i < (int)nums.size() - 1; ++i) {
            farthest = max(farthest, i + nums[i]);
            if (i == currentEnd) {
                ++jumps;
                currentEnd = farthest;
            }
        }

        return jumps;
    }
};

class Solution:
    def jump(self, nums: list[int]) -> int:
        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

var jump = function(nums) {
  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;
};

中文

题目概述

给定数组 nums，每个元素表示从该位置最多可跳的步数。你从下标 0 出发，返回到达最后一个下标所需的最少跳跃次数。

核心思路

把“一次跳跃”看成一层可达区间。扫描当前层区间时维护下一层最远可达位置 farthest；当扫描指针走到当前层边界 currentEnd，就必须增加一次跳跃并把边界推进到 farthest。

暴力解法与不足

用 DP 或显式 BFS 建图都能做，但最坏可能到 O(n^2)。贪心只保留区间边界和最远可达，线性时间即可完成。

最优算法步骤

1）初始化 jumps=0、currentEnd=0、farthest=0。
2）遍历 i=0..n-2。
3）更新 farthest = max(farthest, i + nums[i])。
4）若 i == currentEnd，说明当前层扫描完：jumps++，并令 currentEnd=farthest。
5）遍历结束后 jumps 即答案。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 循环写到 n-1 可能多加一次跳跃。
- 混淆 currentEnd 与 farthest（当前层边界 vs 下一层最远点）。
- 忘记题目保证“总能到达最后一个位置”。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int jump(int[] nums) {
        int jumps = 0;
        int currentEnd = 0;
        int farthest = 0;

        for (int i = 0; i < nums.length - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);
            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;
            }
        }

        return jumps;
    }
}

func jump(nums []int) int {
    jumps, currentEnd, farthest := 0, 0, 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
}

class Solution {
public:
    int jump(vector<int>& nums) {
        int jumps = 0, currentEnd = 0, farthest = 0;

        for (int i = 0; i < (int)nums.size() - 1; ++i) {
            farthest = max(farthest, i + nums[i]);
            if (i == currentEnd) {
                ++jumps;
                currentEnd = farthest;
            }
        }

        return jumps;
    }
};

class Solution:
    def jump(self, nums: list[int]) -> int:
        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

var jump = function(nums) {
  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;
};