Greedy Algorithms
A greedy algorithm builds a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit.
TARGET 6 · COINS 4, 3, 1
TAKE LARGEST
REMAINING
6
Greedy — 0 coins
Empty
Exhaustive optimum
Empty
Make 6 from 4, 3, 1 using as few coins as possible. Greedy always takes the largest coin that still fits.
Next
4 is the largest coin that fits in 6. Take it — greedy never reconsiders this — leaving 2.
Coins
Target
Intuition
Imagine you want to count a pile of money as quickly as possible. You would naturally start by picking the largest denominations first. This is a Greedy approach: making the locally optimal choice at each step with the hope of finding a global optimum.
Concept
Core Properties:
- Greedy Choice Property: A global optimal solution can be arrived at by selecting a local optimal (greedy) choice.
- Optimal Substructure: An optimal solution to the problem contains specific optimal solutions to sub-problems.
Greedy vs. DP:
- Greedy: Makes a choice and never looks back. Generally faster, but doesn't guarantee a global optimum for all problems.
- Dynamic Programming: Considers all possible choices (and solutions to subproblems) to find the guaranteed optimum.
How it Works
General Framework:
- Candidate Set: A list of items to choose from.
- Selection Function: Chooses the best candidate to add to the solution.
- Feasibility Function: Checks if the candidate can contribute to a solution.
- Objective Function: Assigns a value to a solution (maximize or minimize).
Step-by-Step Breakdown
Classic Example (Coin Change):
- Target: 36 cents. Coins: {25, 10, 5, 1}.
- Step 1: Pick largest <= 36. Pick 25. Remaining: 11.
- Step 2: Pick largest <= 11. Pick 10. Remaining: 1.
- Step 3: Pick largest <= 1. Pick 1. Remaining: 0.
- Result: 3 coins (25, 10, 1). Optimal!
When to Use
Standard Problems:
- Activity Selection / Interval Scheduling.
- Huffman Coding (Compression).
- Minimum Spanning Tree (Prim's, Kruskal's).
- Dijkstra's Algorithm (Shortest Path).
When NOT to Use
- Knapsack Problem (0/1): Greedy fails here; requires DP.
- Longest Path: Greedy often fails.
- Any problem where a local optimal choice prevents a global solution.
How to Identify
"Find minimum number of...", "Maximize total...", sorted inputs often suggest Greedy.
Preparing for interviews? This topic is also taught as a pattern:
Introduction to Greedy Algorithms
Applying for software engineering roles? Free, no sign-up:
AI resume checker — match your resume to the job description
Compare its cost with every other algorithm in the Big O cheat sheet.