Greedy Algorithms

Also Known As

TL;DR

Explanation

A greedy algorithm selects the best available option at each step without reconsidering previous choices. It works when: the greedy choice is safe (local optimum leads to global optimum) and the problem has optimal substructure. Classic examples: coin change (if denominations allow), interval scheduling (sort by end time), Huffman coding, Kruskal/Prim for minimum spanning trees. Fails for: general coin change (e.g. coins {1,3,4} — greedy for 6 gives {4,1,1} not optimal {3,3}).

Diagram

flowchart TD
    PROBLEM[Optimisation problem] --> CHOICE[Make locally optimal choice<br/>at each step]
    CHOICE --> IRREV[Never reconsider<br/>irrevocable decision]
    IRREV --> NEXT[Move to next subproblem]
    NEXT -->|done?| SOLUTION[Global solution]
    subgraph Works For
        COIN[Coin change - large denominations first]
        HUFFMAN[Huffman coding]
        DIJKSTRA[Dijkstra shortest path]
        PRIM[Prim minimum spanning tree]
    end
    subgraph Does NOT Work For
        KNAPSACK[0-1 Knapsack - needs DP]
        TSP[Travelling Salesman]
    end
style SOLUTION fill:#238636,color:#fff
style KNAPSACK fill:#f85149,color:#fff
style TSP fill:#f85149,color:#fff

Common Misconception

Why It Matters

Common Mistakes

• Applying greedy to problems where it doesn't hold — coin change with arbitrary denominations requires DP.
• Not sorting before applying greedy — most greedy algorithms require the input in a specific order.
• Confusing greedy with DP — if a problem has overlapping subproblems, DP is required; if choices are independent, greedy may work.
• Not proving the greedy choice property — assuming greedy works without verifying leads to subtly wrong solutions.

Code Examples

// Greedy coin change fails for non-standard denominations:
function greedyChange(int $amount, array $coins): array {
    rsort($coins); // Sort descending
    $result = [];
    foreach ($coins as $coin) {
        while ($amount >= $coin) { $result[] = $coin; $amount -= $coin; }
    }
    return $result;
}
// greedyChange(6, [1,3,4]) returns [4,1,1] — 3 coins
// Optimal: [3,3] — 2 coins. Greedy fails here.

// DP coin change — always optimal:
function dpChange(int $amount, array $coins): int {
    $dp = array_fill(0, $amount + 1, PHP_INT_MAX);
    $dp[0] = 0;
    for ($i = 1; $i <= $amount; $i++) {
        foreach ($coins as $coin) {
            if ($coin <= $i && $dp[$i - $coin] !== PHP_INT_MAX) {
                $dp[$i] = min($dp[$i], $dp[$i - $coin] + 1);
            }
        }
    }
    return $dp[$amount] === PHP_INT_MAX ? -1 : $dp[$amount];
}

References

• ↗ https://en.wikipedia.org/wiki/Greedy_algorithm

Tags

Related Terms