DSA: Greedy Algorithms
Learn to solve optimization problems by making the locally optimal choice at each step.
Greedy Choice Property and Optimal Substructure
A greedy algorithm builds a solution by making the best available choice at each step without reconsidering past decisions. It works correctly only when the problem has two properties.
When Greedy Works
Two required properties: greedy choice property and optimal substructure.
- Greedy choice property: a locally optimal choice leads to a globally optimal solution
- Optimal substructure: optimal solution contains optimal solutions to subproblems
- Greedy vs DP: greedy makes one irreversible choice; DP explores all choices
- Greedy fails when a local optimum blocks the global optimum (use DP then)
Greedy Choice: Minimum Coins
C++Works for standard denominations; fails for arbitrary coin sets (use DP instead).
Activity Selection Problem
Given activities with start and finish times, select the maximum number of non-overlapping activities. Sort by finish time, then greedily pick each activity that starts after the last one ends.
Activity Selection
Sort by finish time. Pick an activity if its start >= finish of the last selected activity.
- Greedy key: always pick the activity that finishes earliest among remaining valid ones
- This leaves the maximum room for future activities
- Time: O(n log n) for sort + O(n) scan
- Equivalent to N Meetings in One Room with the same greedy
Activity Selection
C++Sort by finish time; greedily pick the next compatible activity.
Fractional Knapsack
Unlike 0/1 Knapsack, items can be taken in fractions. Sort by value-to-weight ratio descending and greedily fill the knapsack. This greedy approach gives the optimal solution.
Fractional Knapsack
Greedy works here because fractions are allowed: always take as much of the best ratio item as possible.
- Greedy fails for 0/1 Knapsack (no fractions): use DP instead
- Sort by val/wt ratio descending
- Take whole item if it fits; take a fraction of the last item to fill remaining capacity
- Time: O(n log n)
Fractional Knapsack
C++Sort by value/weight ratio; take greedily, fraction the last item if needed.
Job Sequencing with Deadlines
Schedule jobs (each taking 1 unit of time) to maximize profit. Each job has a deadline by which it must be completed. Sort by profit descending and fill the latest available slot before each deadline.
Job Sequencing
Greedy: process highest profit jobs first; assign each to the latest free slot before its deadline.
- Sort jobs by profit descending
- For each job try slots from min(deadline, maxDeadline) down to 1
- Assign to the first free slot found; skip if none available
- Time: O(n²) naive; O(n log n) with union-find
Job Sequencing with Deadlines
C++Highest profit first; fill latest available slot before deadline.
Huffman Coding
Build a prefix-free binary code where frequent characters get shorter codes. Use a min-heap: always merge the two nodes with the lowest frequency to build the Huffman tree.
Huffman Coding
Min-heap greedy: merge two lowest-frequency nodes repeatedly until one root remains.
- Each leaf = one character; internal nodes aggregate frequencies
- Left branch = 0, right branch = 1 (or vice versa)
- Greedy choice: merging cheapest two nodes minimizes total weighted path length
- Optimal prefix-free code: no codeword is a prefix of another
- Time: O(n log n)
Huffman Coding
C++Min-heap merge loop builds the optimal prefix-free encoding tree.
Minimum Platforms Required
Given train arrival and departure times, find the minimum number of platforms needed so no train waits. Sort both arrays and use a two-pointer sweep.
Minimum Platforms
Sort arrivals and departures separately. Sweep: arrival increments count, departure decrements it.
- Sort arr[] and dep[] independently
- Two pointers i (arrivals) and j (departures)
- If arr[i] <= dep[j]: new train arrives, platforms++, i++
- Else: train departs, platforms--, j++
- Track maximum platforms seen during the sweep
Minimum Platforms
C++Two-pointer sweep on sorted arrivals and departures; track peak concurrency.
Gas Station Problem
Given gas and cost arrays for stations on a circular route, find the starting station index from which you can complete the full circuit. Return -1 if no solution exists.
Gas Station
If total gas >= total cost, a solution exists. Greedy: reset start whenever tank goes negative.
- If sum(gas) < sum(cost): no solution, return -1
- Sweep forward: accumulate tank = gas[i] - cost[i]
- If tank < 0: current start cannot reach i+1; set start = i+1, reset tank
- The last chosen start is the answer (guaranteed unique when solution exists)
- Time: O(n), Space: O(1)
Gas Station
C++Reset start when tank goes negative; valid start found in one pass.
Candy Distribution
Distribute minimum candies to children in a line such that each child gets at least 1, and a child with a higher rating than an adjacent neighbor gets more candies than that neighbor.
Candy Distribution
Two-pass greedy: left-to-right enforces right-neighbor constraint; right-to-left enforces left-neighbor constraint.
- Pass 1 (left to right): if rating[i] > rating[i-1], candy[i] = candy[i-1] + 1
- Pass 2 (right to left): if rating[i] > rating[i+1], candy[i] = max(candy[i], candy[i+1] + 1)
- Both constraints satisfied simultaneously via max in pass 2
- Answer: sum of candy array
- Time: O(n), Space: O(n)
Candy Distribution
C++Left pass handles right neighbors; right pass handles left neighbors with max.
Greedy Problem Map
Each greedy problem has a specific sorting or ordering key that makes the greedy choice valid.
| Problem | Greedy Key | Sort / Order | Time |
|---|---|---|---|
| Activity Selection | Finish earliest first | By finish time asc | O(n log n) |
| Fractional Knapsack | Best ratio first | By val/wt ratio desc | O(n log n) |
| Job Sequencing | Highest profit first | By profit desc | O(n²) |
| Huffman Coding | Merge cheapest nodes | Min-heap on frequency | O(n log n) |
| Min Platforms | Sweep arrivals/departures | Both arrays sorted | O(n log n) |
| Minimum Coins | Largest coin first | Coins desc (standard denoms) | O(n) |
| Gas Station | Reset on negative tank | Single pass | O(n) |
| Candy Distribution | Two-pass left then right | Index order | O(n) |
Knowledge Check
1. The Greedy Choice Property means:
2. Activity Selection: after sorting by finish time, which activities are selected?
3. Fractional Knapsack sorts items by:
4. In Job Sequencing with Deadlines, jobs are processed in which order?
5. Huffman Coding builds the tree by repeatedly:
6. Minimum Platforms problem answer equals:
7. Gas Station problem: a valid start exists only when:
8. Candy Distribution (LeetCode 135) requires each child with a higher rating than their neighbor to have: