Greedy algorithms are one of the most elegant problem-solving strategies in computer science. They are fast, intuitive, and often surprisingly effective—but only when applied to the right problems.
This guide walks you through the recipe for designing greedy algorithms, the common proof techniques, and the classic patterns you must know.
Table of Contents
What Is a Greedy Algorithm?
When you hear “greedy,” you might think of someone who always grabs the biggest slice of cake. Surprisingly, that’s not a bad way to understand greedy algorithms!
In greedy algorithms, we always take the best-looking choice at the moment without worrying about the future. Sometimes this works perfectly, sometimes it doesn’t. The trick is to learn when it works.
A greedy algorithm builds a solution step by step, always choosing the best local option, and never backtracking.
It works when:
- Optimal Substructure: An optimal solution can be built from optimal sub-solutions.
- Greedy-Choice Property: There exists an optimal solution that starts with a locally optimal choice.
A Simple Example: Picking min. possible coins to make a certain amount.
One of the way to take largest coin possible.
Case 1: Suppose you want to make ₹20 using coins of ₹10, ₹5, and ₹1.
- Take one ₹10 → left 10
- Take two ₹5 → done!
Case 2 But what if the coins were {₹1, ₹3, ₹4} and you want ₹6?
- Greedy takes ₹4 → left 2 → then two ₹1 coins → total 3 coins.
- But the best solution is two ₹3 coins → only 2 coins.
Here greedy fails, Lesson: Greedy is not always right. We must check carefully.
The Recipe for Greedy
Whenever you think a problem might be solved with greedy, follow these steps:
Step 1: Understand the problem clearly
- What are you choosing? (coins, jobs, intervals, paths…)
- What do you want to maximize/minimize?
Step 2: Think of a local rule
- Can I sort things or pick one “best so far”?
- Examples:
- Always pick the shortest job first.
- Always pick the earliest finishing interval.
- Always pick the highest value-to-weight ratio.
Step 3: Test on small examples
- Take 3–5 items and try your rule by hand. Does it give the best result?
Step 4: If it always works → prove it or trust a known pattern
- If it sometimes fails → greedy is not correct → try dynamic programming instead.
Classic Greedy Patterns
Interval Scheduling (The Meeting Room Problem)
Imagine you are a manager, you want to attend as many meetings as possible, but meetings overlap.
How do you choose?
- 👉 Greedy Rule: Always pick the meeting that finishes earliest.
- Why? Because then you leave the most time for future meetings.
- This works 100% of the time.
Try out
- LeetCode 435
- LeetCode 452
Activity with Deadlines (The Homework Problem)
Each homework has a deadline and a profit. You can only do one per day.
Which ones do you choose?
- 👉 Greedy Rule: Do the most profitable homework first, but place it as late as possible before its deadline.
That way, you save earlier days for other homework.
Fractional Knapsack (The Bag Problem)
You have a bag of capacity W. You can take fractions of items. Which to take?
- 👉 Greedy Rule: Take items with highest value per weight first.
Shortest Path with Positive Roads (Dijkstra)
Suppose you’re walking in a city where every road takes some positive time.
- 👉 Greedy Rule: Always go to the city you can currently reach with the smallest time.
When Greedy Works
Greedy works if:
- Local best = global best.
- Once you make a choice, you never need to undo it.
This is true in:
- Interval scheduling
- Fractional knapsack
- Dijkstra
- Minimum spanning tree
When Greedy Fails
- Greedy fails when local choice can hurt future choices.
- Examples:
- 0/1 Knapsack
- Coin systems like {1, 3, 4}
- Some scheduling problems
In those cases, we need Dynamic Programming.
Practice
- Easy coin change (canonical system like {1, 2, 5})
- Activity selection (meeting rooms)
- Minimum number of arrows to burst balloons (LeetCode 452)
- Assign Cookies (LeetCode 455)
- Jump Game I & II (LeetCode 55, 45)
- Job sequencing with deadlines
- Fractional knapsack
- Huffman coding (greedy tree building)
- Kruskal’s MST
- Dijkstra’s shortest path
Leet Code
- Leetcode 455: Assign Cookies
- Leetcode 1221: Split a String in Balanced Strings
- Leetcode 561: Array Partition
- Leetcode 860: Lemonade Change
- Leetcode 944: Delete Columns to Make Sorted
- Leetcode 409: Longest Palindrome