L5. Jump Game - II | Greedy Algorithm Playlist

This chapter explores Jump Game II, building directly upon the concepts introduced in Jump Game Part I. While the first variation asks whether you can reach the final index, this problem requires determining the minimum number of jumps needed to reach the end of the array, with the guarantee that the destination is always reachable.

1. Problem Statement & Core Objective

You are given an array of non-negative integers where each element (nums[i]) represents the maximum jump length you can take forward from that index. Your goal is to find the minimum number of jumps required to travel from the starting index (index 0) to the final index (n - 1).

Example Walkthrough

Consider the following test case:

Index:  0  1  2  3
Array: [2, 3, 1, 4]

• Starting Point: At index 0, the value is 2. You can jump to index 1 or index 2.
• Next Step: From index 1 (value 3), you can jump up to 3 steps ahead, reaching the end directly or via index 2.
• Optimal Path: Jump from index 0 -> index 1 -> index 3 (the end). Total jumps = 3.

2. Naive Approach: Recursive Exploration

When faced with interview problems of this nature, the initial intuition is often to explore all possible paths using recursion, evaluating every valid jump distance from every reachable index.

Recursive Mental Model

• At index 0, you have multiple choices depending on the value of nums[0].
• For each choice, you make a recursive call, incrementing your jump counter by 1.
• Once you reach or exceed the last index, you return the accumulated jump count and take the minimum across all valid branches.

Naive Recursive Code

int solve(int index, int jumps, vector<int>& nums) {
    int n = nums.size();
    // Base Case: If we reach or cross the last index
    if (index >= n - 1) {
        return jumps;
    }
    
    int mini = INT_MAX;
    // Try all possible jumps from the current index
    for (int i = 1; i <= nums[index]; i++) {
        mini = min(mini, solve(index + i, jumps + 1, nums));
    }
    
    return mini;
}
// Called initially as: solve(0, 0, nums)

Complexity Analysis of Recursion

• Time Complexity: $O(n^n)$ in the worst case, as every index can branch out up to $n$ times.
• Space Complexity: $O(n)$ auxiliary stack space due to recursion depth.

3. Dynamic Programming Optimization ($O(n^2)$)

To eliminate redundant computations in the recursive tree, we can apply memoization.

Identifying Overlapping Subproblems

The recursive state is defined by two changing variables:

1. index: Where you are currently standing in the array.
2. jumps: How many jumps you have taken so far.

By introducing a 2D DP memoization table (dp[index][jumps]), we can store previously computed states.

Memoized DP Code Structure

int solveDP(int index, int jumps, vector<int>& nums, vector<vector<int>>& dp) {
    int n = nums.size();
    if (index >= n - 1) return jumps;
    
    if (dp[index][jumps] != -1) return dp[index][jumps];
    
    int mini = INT_MAX;
    for (int i = 1; i <= nums[index]; i++) {
        mini = min(mini, solveDP(index + i, jumps + 1, nums, dp));
    }
    
    return dp[index][jumps] = mini;
}

Complexity Analysis of DP

• Time Complexity: $O(n^2)$ due to the unique states stored in the DP table.
• Space Complexity: $O(n^2)$ for the 2D memoization table.

While an $O(n^2)$ solution passes basic constraints, interviewers typically expect an optimal $O(n)$ linear solution.

4. Transitioning to a Range-Based Greedy Mental Model

Instead of exploring every individual path recursively, we can reframe the problem using ranges (levels). Think of your jumps as expanding concentric ripples or distance tiers.

Real-Life Analogy: Relay Checkpoints

Imagine traveling across a highway where each milestone gives you a fuel voucher allowing you to drive up to $X$ miles further. Instead of calculating every single turn, you divide your journey into check-point ranges:

• Range 1: What is the furthest point I can reach with 1 jump?
• Range 2: Within that reachable zone, what is the absolute furthest point I can push my boundary with 2 jumps?

By maintaining a sliding window defined by a left (L) and right (R) boundary, we evaluate the maximum reach dynamically without recalculating past indices.

5. Step-by-Step Greedy Algorithm Walkthrough

Let's trace the optimal linear algorithm using our example array: [2, 3, 1, 4].

1. Initialization:

   • jumps = 0
   • L = 0, R = 0 (Our current reachable range is indices 0 to 0).

2. First Iteration (Jump 1):

   • We scan all elements within the current range (L to R, which is just index 0).
   • At index 0, nums[0] = 2. The farthest we can reach is index + nums[index] = 0 + 2 = 2.
   • Update our boundaries: The new range starts right after R (L = R + 1 = 1), and the new right boundary becomes our farthest reach (R = 2).
   • Increment jumps to 1.

3. Second Iteration (Jump 2):

   • Current range is L = 1 to R = 2.
   • We scan elements in this range (index 1 and index 2):
     • At index 1 (nums[1] = 3), farthest reach is 1 + 3 = 4.
     • At index 2 (nums[2] = 1), farthest reach is 2 + 1 = 3.
   • The maximum farthest reach found across this range is 4 (which covers or exceeds the end of the array n - 1).
   • Update boundaries and increment jumps to 2.
   • Since our right boundary R has reached or exceeded n - 1, we terminate and return jumps.

6. Complete Production-Ready Code

Here is the clean, optimal $O(n)$ greedy implementation in C++:

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return 0;
        
        int jumps = 0;
        int l = 0, r = 0;
        
        // Continue until the right boundary reaches or exceeds the last index
        while (r < n - 1) {
            int farthest = 0;
            
            // Scan all elements in the current [l, r] range
            for (int i = l; i <= r; i++) {
                farthest = max(farthest, i + nums[i]);
            }
            
            // Move the left boundary to the element right after current r
            l = r + 1;
            
            // Expand the right boundary to the farthest reachable index
            r = farthest;
            
            // Count this tier/range as a completed jump
            jumps++;
        }
        
        return jumps;
    }
};

7. Complexity Analysis Summary

8. Summary and Key Takeaways

• Problem Distinction: Unlike Jump Game I (which checks binary reachability), Jump Game II requires calculating the minimum jumps to destination.
• Greedy Choice Property: At any given tier, we greedily look for the farthest possible reach (i + nums[i]) to maximize our coverage before committing to another jump.
• Range Management (L and R): Instead of tracking individual paths, framing the problem around expanding level ranges (L to R) collapses time complexity from exponential down to linear $O(n)$.
• Constant Space: The greedy two-pointer approach requires no auxiliary data structures, achieving $O(1)$ space complexity.
• Early Termination: The loop terminates instantly as soon as the right range boundary R covers or surpasses the final array index (n - 1).