Imagine a shopkeeper has to give you ₹289 as change, using as few notes and coins as possible.
Without thinking too hard, most people would do this:
Take the biggest note that fits: ₹200 (remaining 89)
Take the biggest note that fits: ₹50 (remaining 39)
Take the biggest note that fits: ₹20 (remaining 19)
Take the biggest note that fits: ₹10 (remaining 9)
Take the biggest coin that fits: ₹5 (remaining 4)
Take the biggest coin that fits: ₹2 (remaining 2)
Take the biggest coin that fits: ₹2 (remaining 0)At every step, we simply took the best-looking option right now, and never went back to change an earlier decision.
That style of problem solving is called a greedy algorithm.
A greedy algorithm builds a solution step by step, always making the choice that looks best at the current moment, and never reconsidering earlier choices.
You have already seen greedy algorithms in this course without knowing the name: Prim's and Kruskal's algorithms (Minimum Spanning Tree) and Dijkstra's algorithm are all greedy.
How a Greedy Algorithm Works
Almost every greedy algorithm follows the same pattern:
1. Decide what "best choice right now" means
(smallest, largest, earliest, highest ratio, ...)
↓
2. Usually sort the input by that rule
(or use a priority queue)
↓
3. Go through the items one by one
↓
4. Take the item if it is allowed (does not break a rule)
↓
5. Never undo a decisionBecause there is no going back and no trying of alternatives, greedy algorithms are usually simple and fast, often O(n log n) because of the sorting step.
Greedy vs Backtracking
In the Backtracking chapter, we explored all possible choices and undid the ones that did not work.
Backtracking | Greedy |
|---|---|
Tries many choices, undoes bad ones | Makes one choice per step, never undoes |
Always finds the correct answer (if it explores everything) | Correct only if the problem has the right properties |
Often exponential time | Usually O(n) or O(n log n) |
So greedy algorithms trade safety for speed. The big question is: when is the greedy choice safe?
When Does Greedy Work?
A greedy algorithm gives the optimal answer when the problem has two properties.
1. Greedy Choice Property
A globally optimal solution can be reached by making the locally best choice at each step.
In other words, taking the "best-looking" option now never stops you from reaching the best final answer.
2. Optimal Substructure
An optimal solution to the whole problem contains optimal solutions to its smaller subproblems.
After making the greedy choice, what is left is a smaller version of the same problem, and solving it optimally gives the overall optimum.
If either property is missing, greedy can give a wrong answer, and it will not warn you.
When Greedy Fails: A Warning Example
Let's go back to giving change, but with a strange coin system:
Coins: 1, 3, 4
Amount: 6Greedy (take the biggest coin that fits):
4 → remaining 2
1 → remaining 1
1 → remaining 0
Greedy answer: 4 + 1 + 1 = 3 coinsBut the best answer is:
3 + 3 = 2 coinsTaking the biggest coin (4) looked best at that moment, but it forced us into a worse result later.
So the same greedy idea works for Indian currency but fails for {1, 3, 4}. Coin systems where greedy always works (like ₹1, 2, 5, 10, 20, 50, 100, 200, 500) are called canonical coin systems. For general coin systems, we need Dynamic Programming, which we study in upcoming chapters.
Here is a Java program that shows both cases:
import java.util.ArrayList;
class Main {
// coins must be sorted in descending order
static ArrayList<Integer> greedyChange(int[] coins, int amount) {
ArrayList<Integer> used = new ArrayList<>();
for (int coin : coins) {
while (amount >= coin) {
amount -= coin;
used.add(coin);
}
}
return used;
}
public static void main(String[] args) {
int[] indian = {500, 200, 100, 50, 20, 10, 5, 2, 1};
ArrayList<Integer> a = greedyChange(indian, 289);
System.out.println("289 -> " + a + " (" + a.size() + " coins/notes)");
int[] odd = {4, 3, 1};
ArrayList<Integer> b = greedyChange(odd, 6);
System.out.println("6 with {4, 3, 1} -> " + b + " (" + b.size() + " coins)");
}
}Output:
289 -> [200, 50, 20, 10, 5, 2, 2] (7 coins/notes)
6 with {4, 3, 1} -> [4, 1, 1] (3 coins)Lesson: a greedy algorithm that "feels right" can still be wrong. Always test it against small tricky examples, or prove it.
Problem 1: Activity Selection
This is the most famous greedy problem, and a favorite in interviews.
Problem: You are given n activities (meetings, classes, events), each with a start time and an end time. You can attend only one activity at a time. What is the maximum number of activities you can attend?
Activity: A B C D E F
Start: 1 3 0 5 8 5
End: 2 4 6 7 9 9Which Greedy Rule?
There are several rules we could try:
Rule | Works? |
|---|---|
Pick the activity that starts earliest | No. A long early activity can block many short ones. |
Pick the shortest activity | No. A short activity can overlap two others that could both have been chosen. |
Pick the activity that ends earliest | Yes. It leaves the most time for the rest. |
Counterexample for "earliest start":
[0 ─────────────── 10]
[1─2] [3─4] [5─6]
Earliest start picks only 1 activity, but 3 are possible.Counterexample for "shortest":
[0 ──── 5] [6 ──── 11]
[4 ─ 7]
Shortest picks [4─7], which blocks both others. Best answer is 2.Step by Step
Sort by end time:
A (1, 2)
B (3, 4)
C (0, 6)
D (5, 7)
E (8, 9)
F (5, 9)Now go through them, keeping track of when the last chosen activity ends:
A (1, 2): first one, take it. lastEnd = 2
B (3, 4): 3 ≥ 2, take it. lastEnd = 4
C (0, 6): 0 < 4, overlaps, skip.
D (5, 7): 5 ≥ 4, take it. lastEnd = 7
E (8, 9): 8 ≥ 7, take it. lastEnd = 9
F (5, 9): 5 < 9, overlaps, skip.
Answer: 4 activities (A, B, D, E)Activity Selection in Java
import java.util.Arrays;
class Main {
static void selectActivities(int[] start, int[] end) {
int n = start.length;
// Store {start, end} pairs so we can sort them together
int[][] activities = new int[n][2];
for (int i = 0; i < n; i++) {
activities[i][0] = start[i];
activities[i][1] = end[i];
}
// Greedy choice: sort by end time
Arrays.sort(activities, (a, b) -> Integer.compare(a[1], b[1]));
int count = 1;
int lastEnd = activities[0][1];
System.out.println("Selected: (" + activities[0][0] + ", " + activities[0][1] + ")");
for (int i = 1; i < n; i++) {
// Pick it only if it starts after the last chosen one ends
if (activities[i][0] >= lastEnd) {
count++;
lastEnd = activities[i][1];
System.out.println("Selected: (" + activities[i][0] + ", " + activities[i][1] + ")");
}
}
System.out.println("Maximum activities: " + count);
}
public static void main(String[] args) {
int[] start = {1, 3, 0, 5, 8, 5};
int[] end = {2, 4, 6, 7, 9, 9};
selectActivities(start, end);
}
}Output:
Selected: (1, 2)
Selected: (3, 4)
Selected: (5, 7)
Selected: (8, 9)
Maximum activities: 4Here we treat an activity that starts exactly when the previous one ends as non-overlapping (>=). If the problem says touching intervals conflict, use > instead. Always read this detail carefully.
Why "Earliest End" Is Correct
We can prove it with an exchange argument, the standard way to prove greedy algorithms:
Take any optimal schedule. Let its first activity be
X.Let
Gbe the activity that ends earliest overall. SinceGends no later thanX, replacingXwithGcannot create any overlap with the remaining activities.So there is an optimal schedule that starts with
G. The greedy choice is safe.Remove
Gand every activity that overlaps it. The rest is a smaller version of the same problem, and we repeat.
Complexity
Sorting → O(n log n)
One pass → O(n)
Total time → O(n log n)
Extra space → O(n) for the pairs arrayProblem 2: Fractional Knapsack
Problem: A thief has a bag that can carry at most W kg. There are items, each with a weight and a value. The thief is allowed to take a fraction of an item (like taking half a bag of rice). What is the maximum total value?
Item: 0 1 2
Value: 60 100 120
Weight: 10 20 30
Capacity W = 50The Greedy Rule
Since we can take fractions, what matters is value per kg:
Item 0: 60 / 10 = 6 per kg
Item 1: 100 / 20 = 5 per kg
Item 2: 120 / 30 = 4 per kgTake the items with the highest ratio first, and fill the remaining space with a fraction of the next item.
Take all of item 0 → value 60, remaining capacity 40
Take all of item 1 → value 100, remaining capacity 20
Take 20/30 of item 2 → value 120 × 20/30 = 80, remaining 0
Total = 60 + 100 + 80 = 240Fractional Knapsack in Java
import java.util.Arrays;
class Main {
static double fractionalKnapsack(int[] value, int[] weight, int capacity) {
int n = value.length;
Integer[] idx = new Integer[n];
for (int i = 0; i < n; i++) {
idx[i] = i;
}
// Greedy choice: highest value per kg first
Arrays.sort(idx, (a, b) -> Double.compare(
(double) value[b] / weight[b],
(double) value[a] / weight[a]
));
double total = 0;
int remaining = capacity;
for (int i : idx) {
if (remaining == 0) {
break;
}
if (weight[i] <= remaining) {
// Take the whole item
total += value[i];
remaining -= weight[i];
System.out.println("Take all of item " + i + " -> +" + value[i]);
} else {
// Take only the fraction that fits
double part = (double) value[i] * remaining / weight[i];
total += part;
System.out.println("Take " + remaining + "/" + weight[i]
+ " of item " + i + " -> +" + part);
remaining = 0;
}
}
return total;
}
public static void main(String[] args) {
int[] value = {60, 100, 120};
int[] weight = {10, 20, 30};
System.out.println("Maximum value: " + fractionalKnapsack(value, weight, 50));
}
}Output:
Take all of item 0 -> +60
Take all of item 1 -> +100
Take 20/30 of item 2 -> +80.0
Maximum value: 240.0We sort an array of indexes (Integer[]) instead of the values themselves, so value and weight stay linked. Note that Arrays.sort with a comparator needs an object array like Integer[], not int[].
Time complexity is O(n log n) for sorting plus O(n) for the pass.
The 0/1 Knapsack Trap
Now change one rule: each item must be taken completely or not at all. This is the 0/1 knapsack problem.
Greedy by ratio would take item 0 and item 1:
60 + 100 = 160 (weight 30, and item 2 no longer fits)But the best answer is item 1 and item 2:
100 + 120 = 220 (weight 50)Problem | Greedy works? | Correct technique |
|---|---|---|
Fractional knapsack | Yes | Greedy by value/weight ratio |
0/1 knapsack | No | Dynamic Programming (Knapsack Problems chapter) |
This pair is one of the most popular interview questions about greedy algorithms: two problems that look almost the same, but only one can be solved greedily.
Problem 3: Greedy in Graph Algorithms
Some of the most important graph algorithms you have learned are greedy:
Algorithm | Greedy choice at every step |
|---|---|
Kruskal's MST | Take the cheapest remaining edge that does not form a cycle |
Prim's MST | Take the cheapest edge that connects a new vertex to the tree |
Dijkstra's shortest path | Finalize the unvisited vertex with the smallest distance |
Notice that Dijkstra's greedy choice is safe only when all edge weights are non-negative. With negative edges, the greedy property is lost, and we had to switch to Bellman-Ford. This is the same story as the coin example: a greedy rule is only correct under the right conditions.
Problem 4: Huffman Coding (Idea)
Huffman coding is a classic greedy algorithm used in data compression (it is part of formats like ZIP/DEFLATE, JPEG and MP3).
The idea is to give shorter binary codes to more frequent characters.
Repeat until one node is left:
Remove the two nodes with the SMALLEST frequency (min heap)
Join them under a new node whose frequency is their sum
Put the new node back into the heapExample frequencies:
a: 5 b: 9 c: 12 d: 13 e: 16 f: 45Greedy merges:
5 + 9 = 14
12 + 13 = 25
14 + 16 = 30
25 + 30 = 55
45 + 55 = 100The very frequent f ends up near the root (a 1-bit code), while rare characters like a and b get longer codes. This uses the priority queue you learned earlier.
More Classic Greedy Problems
Problem | Greedy rule |
|---|---|
Minimum number of platforms (railway station) | Sort arrivals and departures, sweep through time |
Job sequencing with deadlines | Take the most profitable job first, schedule it as late as possible |
Jump Game | Track the farthest index reachable so far |
Gas Station | If the tank goes negative, restart from the next station |
Assign Cookies | Sort both arrays, give the smallest cookie that satisfies each child |
Non-overlapping Intervals | Same as activity selection: keep intervals with the earliest end |
Minimum arrows to burst balloons | Sort by end, shoot at the end of each group |
How to Approach a Greedy Problem
Find a candidate rule. Ask: what should I pick first? Earliest end? Largest value? Smallest weight? Best ratio?
Try to break it. Before coding, test the rule on 2 to 4 small tricky inputs. If you find a counterexample, try a different rule.
Convince yourself it is correct. Use the exchange argument: show that any optimal solution can be changed to include the greedy choice without getting worse.
Implement. Usually: sort, then one loop.
If no greedy rule survives, the problem probably needs Dynamic Programming or Backtracking.
Common Mistakes
1. Assuming Greedy Is Always Correct
The coin example {1, 3, 4} and 0/1 knapsack both fail. A greedy rule must be justified.
2. Sorting by the Wrong Key
Activity selection must sort by end time, not start time or duration.
3. Ignoring Ties and Boundaries
Does an activity ending at 4 conflict with one starting at 4? The answer changes >= to >.
4. Integer Division in Ratios
value / weight with two ints throws away the decimal part (100 / 30 = 3). Cast to double first.
5. Overflow in Comparators
Writing (a, b) -> a[1] - b[1] can overflow for very large or very negative values. Integer.compare(a[1], b[1]) is always safe.
Greedy vs Other Techniques
Technique | Idea | Typical speed |
|---|---|---|
Greedy | One locally best choice per step, never undone | Fast, often O(n log n) |
Backtracking | Try all choices, undo bad ones | Often exponential |
Divide and Conquer | Split into independent subproblems, combine results | Often O(n log n) |
Dynamic Programming | Solve overlapping subproblems once and reuse answers | Usually polynomial |
We study Divide and Conquer in the next chapter, and Dynamic Programming right after that.
Interview Tips and Practice Problems
When you propose a greedy solution, say why it works. Interviewers love hearing "exchange argument" or a quick counterexample for the wrong rules.
Interval problems (meetings, balloons, intervals) are very often greedy after sorting by end time.
If the problem says "you may take part of an item", think greedy. If it says "take it or leave it", think DP.
Good problems to practice:
Assign Cookies (LeetCode 455)
Jump Game (LeetCode 55) and Jump Game II (LeetCode 45)
Non-overlapping Intervals (LeetCode 435)
Minimum Number of Arrows to Burst Balloons (LeetCode 452)
Gas Station (LeetCode 134)
N meetings in one room, Fractional Knapsack, Minimum Platforms (GeeksforGeeks)
The Main Idea
A greedy algorithm makes the best-looking choice at each step and never looks back.
Choose a greedy rule
↓
Sort (or use a priority queue)
↓
Take each item if it fits the rules
↓
Never undo a choiceGreedy is correct only when the problem has:
1. Greedy choice property
2. Optimal substructureKey examples:
Activity selection → sort by end time greedy works
Fractional knapsack → sort by value/weight greedy works
Indian coin change → biggest coin first greedy works
Coins {1, 3, 4} → biggest coin first greedy FAILS
0/1 knapsack → by ratio greedy FAILS (use DP)Greedy algorithms are simple and fast, but they are only trustworthy when you can explain why the local choice is always safe. If you can find a counterexample, switch to a different technique.