Chapter 44

Home

The Greedy Mindset

A greedy algorithm makes the best local choice at each step, hoping it leads to the best global solution. It never looks back, never reconsiders. When it works, it's usually the fastest solution. When it doesn't, you need DP.

Local vs Global Optima

Imagine climbing a hill in thick fog. You can only see a few metres ahead. Greedy says: "take the steepest step you can see right now." If the terrain is a smooth slope, you'll reach the peak. If it's a jagged ridge, you might end up on a small hill while the real peak is somewhere else.

local max global max Greedy stops here Better solution requires looking ahead

When Greedy Works

Two properties must hold for a greedy algorithm to be correct:

1. Optimal substructure

An optimal solution to the whole problem contains optimal solutions to its subproblems. This is the same property DP requires.

2. Greedy choice property

A globally optimal solution can be built by making the best local choice at each step. No need to reconsider. This is what separates greedy from DP.

Classic Example: Coin Change

Given coin denominations (1¢, 5¢, 10¢, 25¢), make change for a given amount using the fewest coins. Greedy: take the largest coin that fits, repeat.

C++ — greedy coin change (US denominations)

vector<int> coins = {25, 10, 5, 1};

int greedy_change(int amount) {
    int count = 0;
    for (int coin : coins) {
        count += amount / coin;
        amount %= coin;
    }
    return count;
}

// greedy_change(67) = 2 quarters + 1 dime + 1 nickel + 2 pennies = 6

Rust — greedy coin change

fn greedy_change(mut amount: i32) -> i32 {
    let coins = [25, 10, 5, 1];
    let mut count = 0;
    for coin in coins {
        count += amount / coin;
        amount %= coin;
    }
    count
}

🚨 Greedy fails for arbitrary denominations

With denominations [1, 3, 4], greedy makes 6¢ as 4+1+1 = 3 coins. The optimal answer is 3+3 = 2 coins. Greedy works for US/European coin systems because each denomination is at least double the previous — a property called "canonical coin system." For general denominations, you need DP.

The Greedy Checklist

Before writing a greedy solution, ask:

Can I prove the greedy choice property?

Often an exchange argument: "if an optimal solution doesn't make this local choice, I can swap elements without making it worse."

Does the problem reduce to sorting?

Many greedy problems are: sort by some key, then process in order. Activity selection, interval scheduling, fractional knapsack all follow this pattern.

Is there a counterexample?

Try to construct a small input where greedy gives a suboptimal answer. If you can't find one after a few attempts, greedy might be correct.

Key Takeaways

Practice