LeetEye LeetEye
Medium Greedy ~5 min

Jump Game II

greedy jump-game-ii

Problem

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. Return the minimum number of jumps to reach nums[n - 1].

You can assume that you can always reach nums[n - 1].

Examples

Example 1
Input: nums = [2,3,1,1,4]
Output: 2
Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2
Input: nums = [2,3,0,1,4]
Output: 2
Key Insight

BFS-like greedy: each "level" is all positions reachable with same number of jumps.

BFS-like greedy: track current level's boundary. When you hit boundary, increment jumps and set new boundary to farthest reachable.

How to Approach This Problem

Pattern Recognition: When you see keywords like jump game ii greedy, think Greedy.

Step-by-Step Reasoning

1 This problem is like BFS where:
Answer: All of above
BFS gives shortest path. "Levels" are positions reachable with same jump count.
2 We track:
Answer: All of above
Boundary tells when to increment jumps. Farthest becomes new boundary.
3 We increment jump count when:
Answer: We reach the current boundary
Passing the boundary means we need another jump to go further.
4 While traversing, farthest is updated to:
Answer: max(farthest, i + nums[i])
Track the farthest we can reach from any position in current level.
5 We iterate i from 0 to:
Answer: n - 2 (up to second-to-last)
Don't need to process last index. If we reach it, we're done.

Solution

def jump(nums: List[int]) -> int:
    n = len(nums)
    if n <= 1:
        return 0
    
    jumps = 0
    end = 0       # Current level boundary
    farthest = 0  # Farthest reachable in next level
    
    for i in range(n - 1):  # Don't need to process last index
        farthest = max(farthest, i + nums[i])
        
        if i == end:  # Hit boundary, need another jump
            jumps += 1
            end = farthest
    
    return jumps

Complexity Analysis

Time O(n)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice Greedy problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye