Greedy Pattern

The Greedy pattern solves optimization problems by choosing the local optimal path at each step, hoping that these local choices accumulate to form a valid global optimal solution.

Recognition Signals

You should consider this pattern if you see any of the following cues in the problem description:

• The problem asks to maximize or minimize a value (e.g. “maximum profit”, “minimum jumps”).
• The choices are independent: once a decision is made, you do not need to backtrack or change it.
• A dynamic programming solution is possible, but you notice that a simple forward sweep (sorting first or tracking limits) is sufficient.

How It Works

Instead of checking all paths recursively (backtracking) or filling tables (dynamic programming), you make the choice that looks best right now:

• Forward Sweep: Iterate through the collection while updating a state tracker (e.g. the maximum reachable index in Jump Game).
• Sorting First: Sort the items by a key parameter (e.g. end times in Interval Scheduling) to make optimal local selections.

For example, to find if you can reach the end of an array (Jump Game):

1. Track the maximum reachable index: maxReach = 0.
2. Iterate through: nums = [2, 3, 1, 1, 4].
3. At index 0 (val 2): since index 0 <= maxReach, update maxReach = max(0, 0 + 2) = 2.
4. At index 1 (val 3): since index 1 <= maxReach, update maxReach = max(2, 1 + 3) = 4.
5. Since maxReach >= last_index, return true.

Complexity, With Caveats

• Time Complexity: O(n) for a linear scan, or O(n log n) if the data must be sorted first.
• Space Complexity: O(1) auxiliary space, as you only need a few variables to track the current state.

Minimal Code Template

public class GreedyTemplate {
    // Jump Game (Check if end is reachable)
    public boolean canJump(int[] nums) {
        int maxReach = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > maxReach) {
                return false; // current index is unreachable
            }
            maxReach = Math.max(maxReach, i + nums[i]);
        }
        return true;
    }
}

# Jump Game (Check if end is reachable)
def can_jump(nums: list[int]) -> bool:
    max_reach = 0
    for i in range(len(nums)):
        if i > max_reach:
            return False  # current index is unreachable
        max_reach = max(max_reach, i + nums[i])
    return True

#include <vector>
#include <algorithm>

class GreedyTemplate {
public:
    // Jump Game (Check if end is reachable)
    bool canJump(const std::vector<int>& nums) {
        int maxReach = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (i > maxReach) {
                return false; // current index is unreachable
            }
            maxReach = std::max(maxReach, i + nums[i]);
        }
        return true;
    }
};

Where This Pattern Falls Short

• Subproblem dependence (Lack of Greedy Choice Property): If choosing the local best option now restricts the choices for later steps in a way that prevents the optimal solution (e.g. Coin Change where coin values are arbitrary, like [1, 3, 4] for target 6), greedy will fail. You must use Dynamic Programming instead.
• Backtracking required: If you must re-evaluate earlier decisions based on subsequent inputs, greedy is the wrong choice.

Related Patterns, Compared

• 1D Dynamic Programming: choose this instead when the local optimal choice is not guaranteed to lead to a global optimum, requiring you to evaluate and cache all options.
• Intervals: choose this specialized sub-pattern when scheduling overlapping ranges, which almost always requires sorting by start or end times.

Frequently Asked Questions

How do you prove a greedy algorithm is correct? Usually through induction or contradiction (e.g. proving that the greedy choice always “stays ahead” or that any optimal solution can be transformed into the greedy solution without losing quality). In interviews, testing your logic on small counter-examples is usually sufficient.

What is the difference between Greedy and Dynamic Programming? Greedy makes a local choice and never re-evaluates it. Dynamic Programming evaluates all possible choices at each step, using cached solutions of subproblems to solve the overall problem.

What does this pattern test in interviews? It tests your capability to write simple, highly optimized algorithms and mathematically verify that local choices sum to a global solution.