Jump Game II

Difficulty: Medium
Topics: Array, Dynamic Programming, Greedy
Link: https://leetcode.com/problems/jump-game-ii/

Problem Description

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

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at index i, you can jump to any index (i + j) where:

0 <= j <= nums[i] and
i + j < n

Return the minimum number of jumps to reach index n - 1. The test cases are generated such that you can reach index n - 1.

Example 1:


Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 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

Constraints:

1 <= nums.length <= 104
0 <= nums[i] <= 1000
It’s guaranteed that you can reach nums[n - 1].

Solution

1. Problem Deconstruction

Technical Restatement

Given a 0-indexed integer array nums of length n, starting at index 0, each element nums[i] specifies the maximum jump distance from index i. A valid jump from i lands at any index j where i < j ≤ i + nums[i] and j < n. The goal is to compute the minimum number of such jumps required to reach index n - 1.

Beginner-Friendly Explanation

Imagine you’re on a series of stepping stones labeled from 0 to n-1. From stone i, you can leap up to nums[i] stones forward. Find the fewest number of leaps needed to go from the first stone (index 0) to the last stone (index n-1).

Mathematical Formulation

Let J(i) be the minimum jumps to reach index i from index 0. We seek J(n-1), with:

J(0) = 0
For i > 0, J(i) = min{ J(k) + 1 } for all k < i such that k + nums[k] ≥ i

Alternatively, define f(i) as the farthest index reachable in i jumps. Then, the solution is the smallest k such that f(k) ≥ n-1.

Constraint Analysis

1 <= nums.length <= 10^4: Rules out O(n²) solutions for worst-case (10^8 operations may be borderline in Python). Requires O(n) or O(n log n).
0 <= nums[i] <= 1000: Zero values require careful handling (e.g., getting stuck is impossible per problem guarantee).
Guaranteed reachability: Simplifies logic by avoiding unreachable checks.

Edge Cases Implied:

Single-element array (n=1): 0 jumps needed.
All elements are 0 except last (impossible per guarantee, but handled).
Large jumps that exceed array bounds early (e.g., nums[0] >= n-1 → 1 jump).

2. Intuition Scaffolding

Analogies

Real-World (Bus Stops): Each stop (i) has a maximum distance (nums[i]) you can travel. Find the fewest buses to take to reach the last stop.
Gaming (Platform Jumps): Each platform lets you jump to farther platforms. Minimize the number of jumps to finish the level.
Mathematical (Wavefront Propagation): Each jump propagates a “wave” of reachability. The goal is to find the minimal wavefronts needed to cover n-1.

Common Pitfalls

Greedy from Start: Always taking the farthest jump from current position may not be optimal (e.g., [2, 3, 1, 1, 4] → jumping to index 2 from 0 is worse than index 1).
DFS/Brute Force: Recursively trying all paths leads to O(2^n) time.
Dynamic Programming with O(n²): Calculating minJumps[i] by checking all previous indices is too slow for n=10^4.
Misinterpreting Zero: Thinking a zero value always blocks progress (but problem guarantees reachability).
Overlooking Array Bounds: Forgetting to check i + nums[i] < n in loops.

3. Approach Encyclopedia

Approach 1: Brute Force (DFS)

Idea: Recursively try every possible jump from each index.

def jump(nums):
    n = len(nums)
    def dfs(i):
        if i >= n-1:
            return 0
        min_jumps = float('inf')
        for j in range(1, nums[i] + 1):
            min_jumps = min(min_jumps, 1 + dfs(i + j))
        return min_jumps
    return dfs(0)

Complexity: Time O(2^n), Space O(n) (recursion stack). Fails for n > 20.

Approach 2: Dynamic Programming (O(n²))

Idea: Tabulate dp[i] = min jumps to reach i.

def jump(nums):
    n = len(nums)
    dp = [float('inf')] * n
    dp[0] = 0
    for i in range(n):
        for j in range(1, nums[i] + 1):
            if i + j < n:
                dp[i + j] = min(dp[i + j], dp[i] + 1)
    return dp[-1]

Complexity: Time O(n * max(nums)) ≈ O(10^4 * 1000) = O(10^7) worst-case (acceptable in C++ but borderline in Python). Space O(n).

Approach 3: Greedy BFS (O(n))

Idea: Track current jump’s coverage (current_end), farthest reachable (farthest), and jump count.

Initialize:
  jumps = 0
  current_end = 0  # farthest index reachable with current jumps
  farthest = 0     # overall farthest index reachable

For each index i from 0 to n-2:
  Update farthest = max(farthest, i + nums[i])
  If i == current_end: 
      jumps += 1
      current_end = farthest

Why it works: Each “jump” corresponds to expanding the frontier of reachable indices. Complexity: Time O(n), Space O(1).

Visualization for nums = [2, 3, 1, 1, 4]:

i=0: farthest = max(0, 0+2)=2, current_end=0 → jump=1, current_end=2
i=1: farthest = max(2, 1+3)=4 → if i==2? No
i=2: farthest = max(4, 2+1)=4 → i==2 (current_end) → jump=2, current_end=4
Now i=3,4 are within current_end=4 → done.

4. Code Deep Dive

Optimal Solution (Greedy BFS)

def jump(nums):
    n = len(nums)
    jumps = 0
    current_end = 0
    farthest = 0
    for i in range(n - 1):  # No need to process last element
        farthest = max(farthest, i + nums[i])
        if i == current_end:
            jumps += 1
            current_end = farthest
    return jumps

Line-by-Line Analysis:

n = len(nums): Store array length.
jumps = 0: Initialize jump count.
current_end = 0: End of current jump’s coverage.
farthest = 0: Farthest index reachable overall.
Loop for i in range(n - 1): Iterate until second-last element (since reaching last doesn’t require a jump).
farthest = max(farthest, i + nums[i]): Update farthest reachable index.
if i == current_end:: Exhausted current jump’s coverage.
jumps += 1: Increment jump count.
current_end = farthest: Extend coverage to farthest.
Return jumps: Minimum jumps computed.

Edge Case Handling:

Single Element (n=1): Loop runs for i in range(0) → skipped, returns 0.
Example 2 ([2,3,0,1,4]):
- i=0: farthest=2, i==0 → jumps=1, current_end=2.
- i=1: farthest=max(2, 1+3)=4.
- i=2: farthest=4, i==2 → jumps=2, current_end=4.
- Returns 2.

5. Complexity War Room

Hardware-Aware Analysis

Time O(n): 10^4 iterations ≈ 0.1 ms on modern CPUs.
Space O(1): 3 integers (12 bytes), fits in registers.

Approach Comparison Table

Approach	Time Complexity	Space Complexity	Readability	Interview Viability
Brute Force (DFS)	O(2^n)	O(n)	7/10	❌
DP (O(n²))	O(n * max(nums))	O(n)	8/10	⚠️ (Borderline)
Greedy BFS	O(n)	O(1)	9/10	✅

6. Pro Mode Extras

Variants

Jump Game I (LC 55): Check if reachable (modify greedy to check if farthest >= n-1 early).
Jump Game III (LC 1306): Can jump left or right (BFS/DFS).
Jump Game IV (LC 1345): Minimum jumps to reach end with same-value jumps (BFS).

Interview Cheat Sheet

Mention: “Greedy BFS is optimal with O(n) time and O(1) space.”
Key Insight: “Treat each jump as expanding a frontier of reachable indices.”
Test Cases:
- [0] (returns 0)
- [1, 2, 3] (returns 2)
- All ones (returns n-1)

Optimization Insights

Early termination: If farthest >= n-1 during loop, return jumps + 1.
For large nums[i], clamp i + nums[i] to n-1 to avoid unnecessary checks.

#45 - Jump Game II