Overview
A Greedy Algorithm is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. It makes a locally optimal choice in the hope that this will lead to a globally optimal solution.
Core Concepts
- Greedy Choice Property: A global optimum can be arrived at by selecting a local optimum.
- Optimal Substructure: Like DP, greedy algorithms require that the optimal solution to the problem contains optimal solutions to subproblems.
- No Backtracking: Once a choice is made, it is never reconsidered. This makes greedy algorithms significantly faster than DP or backtracking.
- Complexity: Usually very efficient, often $O(n)$ or $O(n \log n)$ if sorting is required.
Code Examples
// Coin Change Problem (Greedy - only works for some currency systems like USD)
function getMinCoins(amount: number): number[] {
const coins = [25, 10, 5, 1];
const result = [];
for (const coin of coins) {
while (amount >= coin) {
amount -= coin;
result.push(coin);
}
}
return result;
}Use Cases
- Huffman Coding: Optimal prefix codes for data compression.
- Kruskal’s & Prim’s Algorithms: Finding the Minimum Spanning Tree (MST) of a graph.
- Dijkstra’s Algorithm: Finding the shortest path from a source node to all others.
Gotchas
- Global Optimality: Greedy algorithms do not always find the best overall solution. For example, in the 0/1 Knapsack problem, a greedy approach fails, whereas DP succeeds.
- Dependent Choices: If the best choice now limits future options in a way that ruins the outcome, greedy will fail.