Greedy Reachability Analysis

Welcome back! In our recent lessons, we've explored greedy algorithms that often rely on sorting the input to make optimal local choices, such as picking activities by their end times or tracking meeting room overlaps. Today, we're going to investigate a different, but equally powerful, type of greedy strategy that doesn't require sorting.

This lesson focuses on solving reachability problems. You'll learn how to determine if a target is reachable by making a sequence of choices, using a greedy approach that maintains a single piece of information: the farthest position reached so far. We'll use the classic "Jump Game" problem as our primary example to master this technique. This pattern is elegant, highly efficient, and a great tool for your algorithmic toolkit.

The Jump Game Problem

Imagine you're playing a simple board game. You are given an array of non-negative integers, where each number represents the maximum number of steps you can jump forward from that position. Starting at the first index, your goal is to determine if you can reach the very last index.

For example, given the array [2, 3, 1, 1, 4], you start at index 0. You can jump a maximum of 2 steps, landing on index 1 or 2. If you jump to index 1, you can then jump a maximum of 3 steps, which is more than enough to reach the end. So, the answer is true.

Conversely, for the array [3, 2, 1, 0, 4], no matter what jumps you make, you'll eventually land on index 3, which has a jump length of 0. From there, you are stuck and can never reach the final index. The answer here is false.

The video below provides a great visual introduction to the problem and its rules.

From Brute Force to a Greedy Insight

Your first instinct might be to try every possible path. From the start, you could explore all possible jumps, and from each of those landing spots, explore all subsequent jumps, and so on. This is a recursive, brute-force approach. While it would eventually find a path if one exists, it's incredibly inefficient. The number of paths can grow exponentially, leading to a very slow solution.

The video you just saw briefly touches on this and why it's not a good idea.

This inefficiency signals that we need a more clever approach. Instead of tracking every path, what if we only tracked the most optimistic summary of all paths so far?

The Greedy Strategy: Farthest Reachable Position

The key insight for a greedy solution is to reframe the question. Instead of "is there a path to the end?", we ask, "as I move forward, what is the farthest index I can possibly reach?"

Here’s the strategy:

1. Initialize a variable, farthest_reach, to 0. This represents the farthest index we can get to. Initially, we are at index 0, so we can reach index 0.
2. Iterate through the array with an index i from the start to the end.
3. At each index i, first check if we can even get here. If our current index i is greater than farthest_reach, it means we've hit a gap that no previous jump could cross. The end is unreachable, so we can stop and return false.
4. If we can reach index i, we have a new opportunity to extend our reach. From i, we can jump up to nums[i] steps forward, reaching i + nums[i]. We update our farthest_reach to be the maximum of its current value and this new potential reach: farthest_reach = max(farthest_reach, i + nums[i]).
5. If we complete the loop without ever getting stuck (i.e., i never exceeds farthest_reach), it means the last index was always within our expanding reach. We can therefore conclude that the end is reachable.

This article from AlgoMonster provides an excellent explanation of this idea, which it calls "reachable zones."

Visualizing the Algorithm

Let's trace this logic on an example: nums = [3, 2, 1, 4, 2, 1, 0, 5]. The last index is 7.

• i = 0: farthest_reach is 0. We are at index 0, which is not beyond our reach (0 <= 0). Update reach: farthest_reach = max(0, 0 + nums[0]) = max(0, 3) = 3. We can now reach up to index 3.
• i = 1: We are at index 1. This is reachable (1 <= 3). Update reach: farthest_reach = max(3, 1 + nums[1]) = max(3, 3) = 3. No change.
• i = 2: We are at index 2. This is reachable (2 <= 3). Update reach: farthest_reach = max(3, 2 + nums[2]) = max(3, 3) = 3. No change.
• i = 3: We are at index 3. This is reachable (3 <= 3). Update reach: farthest_reach = max(3, 3 + nums[3]) = max(3, 7) = 7. Now we can reach up to index 7!

At this point, our farthest_reach is 7, which is the last index. We already know the answer is true. The image below visualizes the rest of the process from the next step.

Why is This Greedy Approach Safe?

This feels almost too simple, which can be a source of anxiety. Are we sure we're not missing a better path by not exploring all options? The article from John Kavanagh provides a concise and practical argument for why this greedy state is "safe."

In essence, because you can only jump forward, the farthest point you can reach from the first i positions is all that matters for reaching positions i+1 and beyond. You don't need to remember the specific path taken to get there.

Implementation in TypeScript

Now, let's translate this logic into a clean TypeScript function. This implementation directly follows the steps we've outlined.

function canJump(nums: number[]): boolean {
    // If the array has only one element, we are already at the last index.
    if (nums.length <= 1) {
        return true;
    }

    let farthest_reach = 0;

    for (let i = 0; i < nums.length; i++) {
        // If the current index is beyond the farthest we could have reached,
        // it's impossible to continue.
        if (i > farthest_reach) {
            return false;
        }

        // Update the farthest reach with the potential new maximum from this index.
        farthest_reach = Math.max(farthest_reach, i + nums[i]);

        // An optional optimization: if our reach already covers the last index,
        // we can return true immediately.
        if (farthest_reach >= nums.length - 1) {
            return true;
        }
    }

    // This line is technically unreachable if the optimization above is used,
    // but if the loop completes without the optimization, it means the end is reachable.
    return true;
}

// Example 1: Reachable
console.log(canJump([2, 3, 1, 1, 4])); // Output: true

// Example 2: Unreachable
console.log(canJump([3, 2, 1, 0, 4])); // Output: false

The time complexity is $O(n)$ because we iterate through the array once. The space complexity is $O(1)$ as we only use a few extra variables.

Common Pitfalls

This algorithm is simple, but small mistakes in logic can lead to incorrect results. Being aware of them is key to building confidence and avoiding bugs in an interview setting.

The AlgoMonster article has a fantastic section on this.

The most critical pitfall is the reachability check: if (i > farthest_reach). It must be a strict > because if i == farthest_reach, it means we can just reach the current index i, which is valid. Using >= would incorrectly fail on cases like [2, 0, 0].

Conclusion

In this lesson, we tackled a new class of greedy problems centered on reachability. By shifting our focus from exploring all paths to simply maintaining the farthest reachable point, we developed a highly efficient and elegant solution.

Here are the key takeaways:

• The "Farthest Reach" Pattern: For problems asking "can I get from A to B?", a greedy strategy that tracks the maximum reach so far is often very effective.
• Greedy State vs. Greedy Choice: Unlike previous problems where we made a specific choice (like picking an interval), here our greedy action was to update a state (farthest_reach) that summarized the best possible outcome of all choices made so far.
• Algorithm Steps: In a single pass, check if the current position is reachable. If so, update the farthest reach. If not, you're stuck.
• Efficiency: This approach provides a linear time $O(n)$ and constant space $O(1)$ solution, a significant improvement over brute-force or dynamic programming alternatives.

You've now added another important pattern to your greedy algorithm toolkit. In our next lesson, we'll shift gears to another fundamental topic: graph connectivity. You will learn about the Disjoint-Set Union (DSU) data structure, a powerful tool for efficiently tracking and merging groups of connected elements, which is essential for solving problems involving networks and cycles.