Jump Game II

LeetCode 45: Jump Game II Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses a greedy approach to track the current jump's reachable range and the furthest possible reach for the next jump, incrementing the jump count only when the current range is exhausted.

In LeetCode 45, also known as Jump Game II, you are provided with a 0-indexed array of non-negative integers. Each element at a specific index represents the maximum distance you can jump forward from that position. Starting at the first index, your goal is to reach the last index in the minimum number of jumps. Unlike the basic Jump Game, you are guaranteed that a solution exists.

This is a classic algorithmic challenge often used in technical interviews to test understanding of array manipulation and greedy optimization strategies.

Brute Force Approach for Jump Game II

The naive approach to solving Jump Game II involves exploring every possible jump sequence to find the shortest one. This can be modeled as a shortest-path problem on a graph or implemented using recursion.

From index i, we can jump to any index j such that i < j <= i + nums[i]. A recursive function minJumps(i) would calculate: minJumps(i) = 1 + min(minJumps(j)) for all valid j.

Pseudo-code:

function minJumps(index):
    if index >= last_index:
        return 0
    min_steps = infinity
    for j from 1 to nums[index]:
        steps = 1 + minJumps(index + j)
        min_steps = min(min_steps, steps)
    return min_steps

Complexity Analysis: The time complexity is exponential, roughly $O(N^N)$ in the worst case, because the branching factor depends on the values in nums. Even with memoization (Dynamic Programming), the complexity reduces to $O(N^2)$ because for every index i, we iterate through up to nums[i] neighbors.

Why it fails: The constraints state that nums.length can be up to $10^4$. An $O(N^2)$ solution performs roughly $10^8$ operations in the worst case (e.g., an array of all 1s or large jump values), which will likely result in a Time Limit Exceeded (TLE) error on modern judging platforms.

Algorithm Strategy: Greedy Patterns

We implement the strategy using a single pass through the array. We maintain three variables:

1. jumps: The number of jumps made so far.
2. current_end: The index that marks the end of the range reachable with the current number of jumps.
3. farthest: The furthest index we can reach from any position visited so far.

Strategy Details:

• Initialize jumps, current_end, and farthest to 0.
• Iterate through the array from index 0 to n - 2. Note: We stop before the last index because if we have reached the last index, no further jump is needed.
• At each index i, update farthest = max(farthest, i + nums[i]). This builds the potential for the next jump.
• Check if i has reached current_end. If it has:
  • This implies we have finished processing the current level of reachability.
  • We must take a jump to proceed further.
  • Increment jumps.
  • Update current_end to farthest.
• Return jumps.

This approach acts like a Breadth-First Search (BFS) where the "queue" is implicitly represented by the range [current_start, current_end].

Execution Flow

Let's trace nums = [2, 3, 1, 1, 4]. Length n = 5.

1. Initialization:

   • jumps = 0
   • current_end = 0
   • farthest = 0

2. Iteration i = 0:

   • nums[0] = 2. Reach is 0 + 2 = 2.
   • farthest = max(0, 2) = 2.
   • i equals current_end (0). We must jump.
   • jumps becomes 1.
   • current_end becomes farthest (2).
   • State: We are now in the range reachable by 1 jump.

3. Iteration i = 1:

   • nums[1] = 3. Reach is 1 + 3 = 4.
   • farthest = max(2, 4) = 4.
   • i (1) is not current_end (2). Continue.

4. Iteration i = 2:

   • nums[2] = 1. Reach is 2 + 1 = 3.
   • farthest = max(4, 3) = 4.
   • i equals current_end (2). We must jump.
   • jumps becomes 2.
   • current_end becomes farthest (4).

5. Stop:

   • The loop runs up to n - 2 (index 3). Even if we continued, we have reached the target.
   • Return jumps = 2.

Proof of Correctness

The algorithm is correct based on the Greedy Choice Property.

At any step $k$, let the reachable range be $[0, R_k]$. To minimize total jumps, we want the range for step $k+1$, denoted as $[0, R_{k+1}]$, to be as large as possible. $R_{k+1}$ is determined by $\max(i + nums[i])$ for all $0 \le i \le R_k$. Since our algorithm explicitly iterates through every $i$ up to the current boundary ($R_k$) and tracks the maximum possible reach ($R_{k+1}$), we guarantee that the next jump extends the reach maximally. Because the ranges are contiguous and maximized at each step, the first time $R_k \ge n-1$, $k$ is guaranteed to be the minimum number of jumps.

Pattern Reuse Notes

The Greedy - Jump Game Reachability pattern is directly applicable to:

• LeetCode 55: Jump Game: Instead of counting jumps, you simply return true if farthest can reach the last index and false if farthest gets stuck (i.e., farthest <= i). The logic for updating farthest is identical.

Reference Implementation

C++ Solution for LeetCode 45

1class Solution {
2public:
3    int jump(vector<int>& nums) {
4        // Base case: if array length is 1, we are already at the end.
5        if (nums.size() <= 1) return 0;
6        
7        int jumps = 0;
8        int current_end = 0;
9        int farthest = 0;
10        
11        // Iterate up to the second to last element.
12        // If we are at the last element, we don't need to jump again.
13        for (int i = 0; i < nums.size() - 1; ++i) {
14            // Update the furthest index reachable from the current range
15            farthest = max(farthest, i + nums[i]);
16            
17            // If we have reached the end of the current jump's range
18            if (i == current_end) {
19                jumps++;
20                current_end = farthest;
21                
22                // Optional optimization: if we can already reach the end, break
23                if (current_end >= nums.size() - 1) break;
24            }
25        }
26        
27        return jumps;
28    }
29};

Java Solution for LeetCode 45

1class Solution {
2    public int jump(int[] nums) {
3        // If the array has 1 element, no jumps are needed.
4        if (nums.length <= 1) return 0;
5        
6        int jumps = 0;
7        int currentEnd = 0;
8        int farthest = 0;
9        
10        // Iterate to nums.length - 1 to avoid jumping FROM the destination
11        for (int i = 0; i < nums.length - 1; i++) {
12            // Calculate max reach from current position i
13            farthest = Math.max(farthest, i + nums[i]);
14            
15            // If we reach the boundary of the current jump
16            if (i == currentEnd) {
17                jumps++;
18                currentEnd = farthest;
19                
20                // If the new range covers the last index, we can stop early
21                if (currentEnd >= nums.length - 1) break;
22            }
23        }
24        
25        return jumps;
26    }
27}

Python Solution for LeetCode 45

1class Solution:
2    def jump(self, nums: List[int]) -> int:
3        if len(nums) <= 1:
4            return 0
5            
6        jumps = 0
7        current_end = 0
8        farthest = 0
9        
10        # Iterate through the array excluding the last element
11        for i in range(len(nums) - 1):
12            # Update the farthest reachable index
13            farthest = max(farthest, i + nums[i])
14            
15            # If we reach the end of the current jump range
16            if i == current_end:
17                jumps += 1
18                current_end = farthest
19                
20                # Early exit if we can reach the end
21                if current_end >= len(nums) - 1:
22                    break
23                    
24        return jumps