Jump Game

Concept

LeetCode #55.
Problem: You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position. Return true if you can reach the last index, or false otherwise.

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

• Start at index 0 (value 2). You can jump 1 or 2 steps.
• Jump 1 step to index 1 (value 3).
• Jump 3 steps to the end! Return true.

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

• Start at index 0 (value 3).
• No matter what combination of jumps you make, you will always land on the 0.
• You are trapped. Return false.

The DP Approach (Too Slow)

You could solve this using Backtracking/Dynamic Programming.
You stand at index 0, simulate jumping 2 steps, recursively test that path… then simulate jumping 1 step, recursively test that path.
This explores every single possibility. It works, but it takes $O(N^2)$ time. On a massive array, it will Time Limit Exceed.

The Greedy Approach

We don’t need to simulate every path. We just need to track one single mathematical concept: What is the absolute maximum index we can physically reach right now?

We create a variable maxReach starting at 0.
We iterate through the array.
At every index i:

1. If our maxReach is less than i, it means we are physically standing on a square we couldn’t even reach! We are trapped. Return false.
2. Otherwise, we calculate: “From this square, what is the furthest I can jump?” (i + nums[i]).
3. We aggressively update maxReach to be the Math.max(maxReach, i + nums[i]). This is the Greedy Choice. We don’t care how we got there, we just care that we can get there.

Implementation

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

function canJump(nums: number[]): boolean {
    let maxReach = 0;

    for (let i = 0; i < nums.length; i++) {
        
        // Did we encounter a gap we couldn't jump over?
        if (i > maxReach) {
            return false;
        }

        // The Greedy Step: Expand our reach as far as mathematically possible
        maxReach = Math.max(maxReach, i + nums[i]);

        // Early Exit Optimization: 
        // If our maxReach is already past the finish line, we won!
        if (maxReach >= nums.length - 1) {
            return true;
        }
    }

    return true;
}

The “Reverse Greedy” Approach

There is an equally brilliant alternative way to solve this. Instead of starting at the beginning and jumping forward, you start at the finish line and work backward!

1. Set goal = nums.length - 1.
2. Iterate backward from nums.length - 2 down to 0.
3. At each index i, ask: “Can I reach the goal from here?” (i + nums[i] >= goal).
4. If YES: That means index i is a safe stepping stone. We move the goal post closer to us! (goal = i).
5. If the goal eventually reaches 0, it means we successfully walked a continuous path all the way back to the start.

function canJumpReverse(nums: number[]): boolean {
    let goal = nums.length - 1;

    for (let i = nums.length - 2; i >= 0; i--) {
        if (i + nums[i] >= goal) {
            goal = i; // Move the goalpost closer!
        }
    }

    return goal === 0;
}

Interview Questions

Q: In the Reverse approach, what happens if there are multiple ways to reach the goal from the current position?
A: The Greedy logic mathematically ignores redundant paths. By moving the goal to the absolute closest valid stepping stone (goal = i), we are making the target as incredibly easy to hit as possible for the numbers further left. The reverse approach perfectly encapsulates the optimal substructure of the problem without tracking multiple paths.