Jump Game II

Concept

LeetCode #45.
Problem: You are given a 0-indexed array of integers nums. 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]. The test cases are generated such that you can always reach the last index.

Input: nums = [2,3,1,1,4]

• Jump 1 step from index 0 to 1.
• Jump 3 steps from index 1 to the end.
  Output: 2

In Jump Game I, we just returned a boolean (true/false). We only tracked the maximum reach.
In Jump Game II, we must track the exact number of jumps. This transforms the problem from simple tracking into a Breadth-First Search (BFS) / Level-Order Traversal… but optimized into $O(1)$ space using Greedy logic!

The BFS / Window Strategy

Imagine the jumps as a radius of expanding waves.
Array: [2, 3, 1, 1, 4]

• Jump 0: We are at index 0 (2). We haven’t jumped yet.
• Jump 1 Window: From index 0, we can reach indices 1 and 2. The physical “window” of our first jump is [1, 2].
• To find our next jump, we scan every element inside the current window.
  • Index 1 (3) can reach index 4.
  • Index 2 (1) can reach index 3.
  • The absolute maximum reach from this window is index 4.
• Jump 2 Window: We physically step into our next window ([3, 4]). We increment our jump counter! Since index 4 is the finish line, we stop and return 2.

Implementation

We use three variables:

• jumps: The counter we return.
• currentEnd: The physical boundary of our current “Window”. When our i loop hits this boundary, it means we are forced to take a jump into the next window.
• farthest: The absolute furthest index we have discovered while scanning inside the current window.

// Time Complexity: O(N) (One single pass)
// Space Complexity: O(1)

function jump(nums: number[]): number {
    // If the array is length 1, we are already at the finish line. 0 jumps!
    if (nums.length <= 1) return 0;

    let jumps = 0;
    let currentEnd = 0; // The end boundary of our current jump window
    let farthest = 0;   // The furthest we've discovered we CAN jump

    // Notice we loop to nums.length - 1, NOT nums.length!
    // If we process the final element, we might accidentally 
    // trigger a redundant jump when we are already at the finish line.
    for (let i = 0; i < nums.length - 1; i++) {
        
        // Update the furthest we can mathematically reach from here
        farthest = Math.max(farthest, i + nums[i]);

        // Did we hit the boundary of our current jump window?
        if (i === currentEnd) {
            // We are forced to take a jump!
            jumps++;
            
            // Our new window expands out to the furthest point we discovered
            currentEnd = farthest;
            
            // Early Exit Optimization
            if (currentEnd >= nums.length - 1) {
                break;
            }
        }
    }

    return jumps;
}

Why this is Greedy

This is a Greedy algorithm because it defers the decision of which specific square to jump to.

When we are standing at index 0 (value 2), we know we can jump to index 1 or index 2.
Dynamic Programming would simulate both jumps.
The Greedy algorithm says: “I don’t need to decide yet! I will just scan index 1 and index 2. Whichever one offers the absolute furthest future reach, I will confidently pretend I chose that one.”
It makes the locally optimal choice (maximizing future reach) without actually simulating the path.

Interview Questions

Q: Can you solve this using Dynamic Programming?
A: Yes. You create a dp array initialized to Infinity. dp[0] = 0. For every index i, you loop through all its reachable jumps and do dp[j] = Math.min(dp[j], dp[i] + 1). However, because of the nested loop, this DP approach takes $O(N^2)$ time, making it drastically inferior to the $O(N)$ Greedy approach.

Q: Why does the for loop stop at nums.length - 1 instead of nums.length?
A: If we process the very last element (the finish line), the if (i === currentEnd) check might trigger. If it triggers, it increments jumps++, falsely registering an extra jump after we already crossed the finish line! By stopping exactly one element early, we guarantee we only count the jumps required to land on the finish line.