💬 Discord
Sign In
NeetCode #781LC-45MediumGreedyNC 150NC 250
← Back to All Problems

#781 · #45 · Jump Game II(跳跃游戏 II)

📌 Problem Statement & Constraints

Given a 0-indexed array nums where nums[i] is the maximum jump length from index i, return the minimum number of jumps to reach the last index. The answer is guaranteed reachable. Constraints: 1 <= nums.length <= 10^4, 0 <= nums[i] <= 1000.

💡 Core Algorithmic Approaches

  1. Think of it as a BFS over jump layers: one jump reaches everything up to the current frontier.
  2. Track cur_end (the end of the current jump's reach) and cur_far (the furthest index reachable with one more jump).
  3. Scan left to right; when the scan reaches cur_end, you must jump, so increment the count and extend the frontier to cur_far.
  4. This greedy is optimal because any position within the current frontier costs the same number of jumps.

💻 Benchmark Python3 Implementation

class Solution:
    def jump(self, nums: List[int]) -> int:
        jumps = 0
        cur_end = 0
        cur_far = 0
        for i in range(len(nums) - 1):     # last index needs no jump
            cur_far = max(cur_far, i + nums[i])
            if i == cur_end:
                jumps += 1
                cur_end = cur_far
        return jumps

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): a single pass.
💾 Space Complexity
O(1): three scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Iterating over the whole array including the last index: reaching the last index needs no further jump, so the loop stops at len(nums) - 1.
  • Counting a jump at the start: initialising jumps = 1 double counts; with the frontier formulation it starts at 0.
  • Jumping to the farthest index rather than tracking the frontier: the correct greedy is over ranges, not single positions.
  • Using BFS with an explicit queue: correct but O(n) space and more code.