DSA Notes
Understand greedy algorithms — the greedy choice property, optimal substructure, when greedy works vs fails, and techniques to prove correctness.
What is a Greedy Algorithm?
A greedy algorithm builds a solution piece by piece, always choosing the next piece that offers the most immediate benefit — the locally optimal choice — without reconsidering past decisions. Unlike dynamic programming (which considers all options) or backtracking (which undoes decisions), greedy commits permanently to each choice.
Think of it like shopping on a budget: if you want the most items possible, you always grab the cheapest item next. You never put something back. This "cheapest first" strategy is greedy — and for this particular problem, it actually gives the optimal answer.
Two Conditions for Greedy to Work
A greedy algorithm produces a globally optimal solution only when the problem satisfies:
1. Greedy Choice Property
A locally optimal choice at each step leads to a globally optimal solution. In other words, there exists an optimal solution that includes the greedy choice — you never need to reconsider.
Example: In Activity Selection, always picking the activity that finishes earliest leaves the maximum remaining time for other activities. Any optimal solution can be modified to include this greedy choice without worsening it.
2. Optimal Substructure
After making the greedy choice, the remaining sub-problem has the same structure as the original. The overall optimal solution contains optimal solutions to sub-problems.
Example: After selecting the earliest-finishing activity, the remaining problem is "select maximum activities from those that start after this one finishes" — same problem, smaller input.
When Greedy Fails
Not every optimization problem yields to greedy. Consider the 0/1 Knapsack:
| Items | (weight=10, value=60), (weight=20, value=100), (weight=30, value=120) |
| Capacity | 50 |
| Ratios | 6.0, 5.0, 4.0 |
| Greedy total | 160 |
| Optimal (DP): Pick items 2+3 | value=220, weight=50 ✓ |
Greedy fails here because you cannot take fractions — the greedy choice (item 1) blocks a better combination. This is why 0/1 Knapsack requires dynamic programming.
Greedy vs Dynamic Programming vs Backtracking
| Aspect | Greedy | Dynamic Programming | Backtracking |
|---|---|---|---|
| Decisions | Irrevocable | Consider all options | Try and undo |
| Sub-problems | One (after greedy choice) | Many (overlapping) | Many (tree) |
| Time | Usually O(n log n) | O(n²) or O(n×W) | Exponential |
| Correctness | Only if properties hold | Always optimal | Always finds all |
| Space | O(1) to O(n) | O(n) to O(n²) | O(depth) |
Proof Techniques for Greedy Correctness
Technique 1: Exchange Argument
The most common proof method:
- Assume an optimal solution OPT that differs from the greedy solution.
- Find the first point where they differ.
- Show you can "exchange" OPT's choice for the greedy choice without making it worse.
- Repeat until OPT equals the greedy solution.
Example (Activity Selection): If OPT's first activity finishes later than greedy's first choice, swap it with the greedy choice. Since greedy finishes earlier, it cannot conflict with fewer subsequent activities — so the swap is safe.
Technique 2: Greedy Stays Ahead
Show that at every step, the greedy solution is at least as good as any other partial solution:
- Define a measure of "progress" after k steps.
- Prove by induction that greedy's progress after k steps ≥ any alternative's progress after k steps.
Technique 3: Structural/Cut-and-Paste
Show that any optimal solution can be "cut" and "pasted" to match the greedy solution without loss.
The Generic Greedy Template
def greedy_solve(problem):
# Step 1: Sort or organize by greedy criterion
candidates = sort_by_criterion(problem)
solution = []
for candidate in candidates:
# Step 2: Check feasibility
if is_feasible(solution, candidate):
# Step 3: Commit to choice (irreversible)
solution.append(candidate)
return solutionThe critical design decision is choosing the greedy criterion — what does "best" mean for this problem?
Classic Greedy Problems and Their Criteria
| Problem | Greedy Criterion | Sort By |
|---|---|---|
| Activity Selection | Earliest finish time | Finish time ascending |
| Fractional Knapsack | Highest value/weight ratio | Ratio descending |
| Huffman Coding | Lowest frequency first | Frequency ascending (min-heap) |
| Job Sequencing | Highest profit first | Profit descending |
| Minimum Spanning Tree (Kruskal) | Lightest edge | Edge weight ascending |
| Dijkstra's Shortest Path | Nearest unvisited vertex | Distance (priority queue) |
| Coin Change (canonical systems) | Largest denomination | Denomination descending |
A Simple Example: Coin Change
Given denominations [25, 10, 5, 1] and target 41 cents:
This works for US currency because it is a canonical coin system. For arbitrary denominations like [1, 3, 4] with target 6, greedy gives [4, 1, 1] (3 coins) but optimal is [3, 3] (2 coins). Always verify the greedy choice property before trusting greedy!
Complexity Characteristics
Most greedy algorithms have:
- Sorting step: O(n log n) — often the bottleneck
- Selection loop: O(n) — linear scan through sorted candidates
- Overall: O(n log n) time, O(1) to O(n) space
This makes greedy algorithms extremely efficient when they apply correctly.
Real-World Applications
- Network routing: Dijkstra's algorithm for shortest paths
- Data compression: Huffman coding in ZIP, JPEG, MP3
- Resource scheduling: OS CPU scheduling, meeting room allocation
- Network design: Minimum spanning tree for cable layout
- Caching: LRU/LFU eviction policies have greedy underpinnings
Key Takeaways
Greedy algorithms are elegant and efficient but only correct for problems satisfying the greedy choice property and optimal substructure. Always prove correctness (exchange argument is your friend) before assuming greedy works. When it does work, you get optimal solutions in O(n log n) time — hard to beat.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Greedy Algorithm Fundamentals.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, greedy, introduction, greedy algorithm fundamentals
Related Data Structures & Algorithms Topics