Advanced Greedy Patterns

1. Introduction: Trusting the Intuition

While basic greedy problems (like Fractional Knapsack) rely on sorting, advanced greedy problems often involve making rapid, strictly forward-moving decisions on unsorted arrays.

These problems are notoriously difficult in interviews because they feel like Dynamic Programming problems. You look at them and think, "I need to check all possible jumps," or "I need to check all possible starting gas stations." However, checking all possibilities yields $O(N^2)$ or $O(2^N)$ time. Advanced greedy patterns rely on finding a mathematical invariant—a rule that allows you to confidently discard massive chunks of the search space without ever looking back, achieving an elegant $O(N)$ solution.

2. Core Concept: The Maximum Reach and Invariants

The two most famous advanced greedy patterns are:

1. The Maximum Reach: Used in "Jump Game" style problems. You maintain a single variable maxReach. As you iterate, you update maxReach. If your current index ever exceeds your maxReach, you have hit a dead end and the problem is unsolvable.
2. The Two-Pass / Accumulator: Used in "Gas Station" style problems. You maintain a running total. If the running total goes negative, it implies that no starting point up to your current index could possibly be valid! You reset your starting point to the next index and continue.

3. Advanced Code Example: Jump Game

Problem Statement: (LeetCode 55) 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.

The DP Trap: Beginners try to write a recursive DP function: canReach(index) loops through all possible jumps 1 to nums[index] and calls canReach(index + jump). This is $O(N^2)$ and will Time Limit Exceed.

The Greedy Insight: As we walk through the array, we just need to keep track of the furthest possible index we can reach at the moment. If our current index i is greater than maxReach, it means we are standing on a square we couldn't possibly have reached. We lose. If maxReach eventually surpasses the last index, we win!

public class JumpGame {
    public boolean canJump(int[] nums) {
        int maxReach = 0;
        
        for (int i = 0; i < nums.length; i++) {
            // If the current index is beyond our maximum reach, we are stuck!
            if (i > maxReach) {
                return false;
            }
            
            // From this current index, how far can we reach?
            // Update the global maxReach if this jump takes us further.
            maxReach = Math.max(maxReach, i + nums[i]);
            
            // Early exit optimization: if we can already reach the end, stop checking!
            if (maxReach >= nums.length - 1) {
                return true;
            }
        }
        
        return true;
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$. Single pass.
• Space Complexity: $O(1)$.

4. Advanced Code Example: Jump Game II (Minimum Jumps)

Problem Statement: (LeetCode 45) Return the minimum number of jumps required to reach the last index. (Assume you can always reach the last index).

The Insight: This requires a dual-boundary Greedy approach. We don't just need to know how far we can reach, we need to know when we are forced to make a jump. We maintain our currentEnd (the boundary of our current jump). We iterate through the array, constantly updating the farthest we can reach. The moment our loop index hits the currentEnd, it means we have fully exhausted all options for our current jump, and we MUST commit to another jump (using the farthest distance we found).

public class JumpGameII {
    public int jump(int[] nums) {
        int jumps = 0;
        int currentEnd = 0;  // The limit of our current jump
        int farthest = 0;    // The absolute furthest we can reach from the current window
        
        // Notice we stop at length - 1. We don't need to jump IF we are already on the last index!
        for (int i = 0; i < nums.length - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);
            
            // We have reached the edge of our current jump window
            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest; // Commit to the jump that takes us furthest
                
                if (currentEnd >= nums.length - 1) break;
            }
        }
        
        return jumps;
    }
}

5. Advanced Code Example: Gas Station

Problem Statement: (LeetCode 134) There are n gas stations along a circular route. You have a car with an unlimited gas tank. It costs cost[i] of gas to travel from station i to its next station (i + 1). You begin with an empty tank at one of the gas stations. Return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

The DP Trap: Simulate starting from every single station and doing a nested loop to see if you make it around. $O(N^2)$ time.

The Greedy Invariants:

1. Global invariant: If the total gas provided by all stations is less than the total cost of all roads, a journey is mathematically impossible. Return -1.
2. Local invariant: If I start at Station A, and run out of gas at Station C, no station between A and C can be the starting point! Why? Because starting at B means starting with 0 gas, whereas when we reached B from A, we arrived with $\ge 0$ gas, and we still failed at C. Therefore, if we fail at C, the next possible starting point is C+1!

public class GasStation {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0;
        int totalCost = 0;
        
        int currentTank = 0;
        int startingStation = 0;
        
        for (int i = 0; i < gas.length; i++) {
            totalGas += gas[i];
            totalCost += cost[i];
            
            currentTank += gas[i] - cost[i];
            
            // If we run out of gas...
            if (currentTank < 0) {
                // The current station AND all previous stations are invalid starting points.
                // Reset the starting point to the NEXT station.
                startingStation = i + 1;
                // Reset our tank to 0 for the new attempt
                currentTank = 0; 
            }
        }
        
        // Global invariant check: did we have enough gas overall?
        if (totalGas < totalCost) {
            return -1;
        }
        
        return startingStation;
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$. We make exactly one pass over the arrays.
• Space Complexity: $O(1)$.

6. Common Mistakes Beginners Make

1. Choosing the "biggest jump" immediately in Jump Game II

   • The Mistake: If you are at index 0, and nums[0] = 3, you look at indices 1, 2, and 3. nums[1] = 5, nums[2] = 2, nums[3] = 1. You jump to 1 because 5 is the biggest number.
   • Why it's wrong: You want the jump that takes you furthest overall, which is index + nums[index]. A small jump might land you on a massive number (like a trampoline) further down! The Greedy Choice must evaluate i + nums[i].

2. Looping arrays in Gas Station

   • The Mistake: Using % n arithmetic to physically loop around the array to simulate the circular route.
   • Why it's wrong: The global invariant (totalGas < totalCost) perfectly eliminates the need to physically loop around. If totalGas >= totalCost, a valid starting point is guaranteed to exist, and the greedy local check will find it in a single linear pass.

7. Interview Q&A

Q1: How do I know when to use Greedy vs DP on an unsorted array? Answer: Unsorted array DP usually asks for "All possible ways" or requires checking subsets. Advanced Greedy usually asks for "Is it possible?" (Boolean) or "Minimum steps" where the rules explicitly constrain you to contiguous forward motion. If a problem restricts you to moving purely left-to-right based on local sums or maximums, try finding an invariant for Greedy first.

Q2: What is the "Two-Pass" Greedy Pattern? Answer: (Often used in LeetCode 135 - Candy). You must satisfy a condition based on both your left and right neighbors. You solve it by doing a forward Greedy pass (left-to-right) to satisfy the left neighbor constraints, and then a backward Greedy pass (right-to-left) to satisfy the right neighbor constraints, taking the max of both passes.

Q3: Can Jump Game be solved backward? Answer: Yes! Instead of tracking maxReach from the start, set a goal = nums.length - 1. Walk backward from the end. If i + nums[i] >= goal, you can reach the goal from i! Update goal = i. If goal reaches 0 at the end of the loop, return true.

8. Practice Problems

1. Jump Game I & II (LeetCode 55, 45)
   • Goal: Master the maxReach and currentEnd boundary window logic.
2. Gas Station (LeetCode 134)
   • Goal: Master the invariant failure-reset logic.
3. Candy (LeetCode 135 - Hard)
   • Hint: Master the Two-Pass (Left-to-Right, then Right-to-Left) Greedy approach.

9. Summary

• The Invariant: Advanced greedy algorithms rely on discovering a mathematical rule that allows you to discard invalid states without testing them.
• Jump Game: Instead of simulating the jumps, simulate the boundary of the furthest possible reach.
• Gas Station: A negative running sum implies that the entire sequence of steps that led to that negative sum is invalid as a starting sequence. Reset and continue!