Greedy vs Dynamic Programming
Greedy ✓
- One choice at each step (no lookback)
- Local optimum = global optimum
- Usually O(n) or O(n log n)
- Coin change (canonical coins), activity selection, Huffman coding
- Interval scheduling, jump game
Need DP instead
- Local optimum ≠ global optimum
- Example: coin change with arbitrary denominations
- 0/1 Knapsack (greedy fails)
- Edit distance, LCS, matrix chain
- Requires considering multiple choices
Greedy proof: Exchange argument — assume an optimal solution differs from your greedy solution. Show that swapping to your greedy choice doesn't make it worse. This is the standard proof technique.
Interactive: Jump Game Greedy Reach
Each cell is a max jump length. Watch reach expand greedily as we scan left to right — if reach ever exceeds the last index, we can make it.
Practice Problems
#455Assign CookiesEasy
Assign cookies (sizes) to children (greed factors). Each child needs cookie ≥ greed factor. Maximize content children.
Greedy: Sort both. Use smallest cookie that can satisfy smallest greed. Two pointers.
C++
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(),g.end()); sort(s.begin(),s.end());
int i=0, j=0;
while(i<g.size() && j<s.size()) {
if(s[j]>=g[i]) i++; // satisfied this child
j++;
}
return i;
}
// Time: O(n log n) Space: O(1)
#55Jump GameMedium
Each element is the max jump length from that position. Can you reach the last index?
Greedy: Track the farthest reachable index. If current index > farthest reachable, we're stuck. Otherwise, update farthest.
C++
bool canJump(vector<int>& nums) {
int reach = 0;
for(int i=0; i<nums.size(); i++) {
if(i > reach) return false; // can't reach here
reach = max(reach, i+nums[i]);
}
return true;
}
// Time: O(n) Space: O(1)
#45Jump Game IIMedium
Return minimum number of jumps to reach last index.
Greedy: Track current window end and farthest reachable. When we hit window end, must jump — choose farthest in window as next window.
C++
int jump(vector<int>& nums) {
int jumps=0, curEnd=0, farthest=0;
for(int i=0; i<nums.size()-1; i++) {
farthest = max(farthest, i+nums[i]);
if(i==curEnd) { // must jump now
jumps++;
curEnd=farthest;
}
}
return jumps;
}
// Time: O(n) Space: O(1)
#435Non-overlapping IntervalsMedium
Find minimum number of intervals to remove to make remaining non-overlapping.
Greedy: Sort by end time. Always keep interval with earliest end (leaves more room). Count conflicts when current start < previous end.
C++
int eraseOverlapIntervals(vector<vector<int>>& iv) {
sort(iv.begin(),iv.end(),[](auto&a,auto&b){return a[1]<b[1];});
int remove=0, prevEnd=INT_MIN;
for(auto& i:iv) {
if(i[0]<prevEnd) remove++; // overlap — remove this one
else prevEnd=i[1]; // keep this, update end
}
return remove;
}
// Time: O(n log n) Space: O(1)
#763Partition LabelsMedium
Partition string so each letter appears in at most one part. Return partition sizes.
Greedy: For each char, record last occurrence. Expand current partition to cover last occurrence of all seen chars. When reach end of current partition, cut.
C++
vector<int> partitionLabels(string s) {
int last[26]={};
for(int i=0;i<s.size();i++) last[s[i]-'a']=i;
vector<int> res;
int start=0, end=0;
for(int i=0;i<s.size();i++) {
end=max(end, last[s[i]-'a']);
if(i==end) {
res.push_back(end-start+1);
start=i+1;
}
}
return res;
}
// Time: O(n) Space: O(1)
#134Gas StationMedium
Circular route with gas stations. Find starting station to complete the circuit, or return -1.
Greedy: If total gas ≥ total cost, a solution exists. Starting point: whenever running total goes negative, reset to next station.
C++
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int total=0, tank=0, start=0;
for(int i=0;i<gas.size();i++) {
total += gas[i]-cost[i];
tank += gas[i]-cost[i];
if(tank<0) { start=i+1; tank=0; }
}
return total<0 ? -1 : start;
}
// Time: O(n) Space: O(1)
#135CandyHard
Give children minimum candies. Each child must have ≥ 1. Children with higher rating than neighbor get more candies.
Greedy: Two passes. Left pass: if rating[i] > rating[i-1], candy[i] = candy[i-1]+1. Right pass: if rating[i] > rating[i+1], candy[i] = max(candy[i], candy[i+1]+1).
C++
int candy(vector<int>& ratings) {
int n=ratings.size();
vector<int> c(n,1);
for(int i=1;i<n;i++)
if(ratings[i]>ratings[i-1]) c[i]=c[i-1]+1;
for(int i=n-2;i>=0;i--)
if(ratings[i]>ratings[i+1]) c[i]=max(c[i], c[i+1]+1);
return accumulate(c.begin(),c.end(),0);
}
// Time: O(n) Space: O(n)
Greedy signal words: "minimum number of", "maximum number of", "minimum cost to", "earliest/latest". Sort + one pass or two passes is usually the pattern.
Deeper Understanding
When Greedy Works — and When It Doesn't
The Exchange Argument: How to Prove Greedy Correctness
The technique: show no swap can improve the solution
Assume an optimal solution O differs from your greedy solution G at some step. Show that swapping O's choice for G's choice at that step produces a solution no worse than O. If this holds for every step, G is optimal.
Example: interval scheduling by earliest end time
If optimal O picks interval X and greedy G picks interval Y (with Y ending earlier), swapping X for Y in O leaves at least as much room for future intervals. So O with Y is still optimal — greedy matches optimal.
In interviews: you don't need a full proof
State the greedy choice and why it's locally safe: "sorting by end time ensures we always leave maximum remaining time." Then verify on an example. A counterexample beats a proof — try to break it first.
When Greedy Fails — Know the Counterexamples
Coin change with arbitrary denominations
Greedy (always pick largest coin ≤ remaining) fails with coins=[1,3,4], target=6. Greedy gives 4+1+1=3 coins. Optimal is 3+3=2 coins. Use DP instead.
0/1 Knapsack
Greedy by value/weight ratio fails. Items: (weight=10, value=60), (weight=20, value=100), (weight=30, value=120), capacity=50. Greedy picks 60+100=160. Optimal is 100+120=220 (take last two).
Shortest path with negative weights
Dijkstra (greedy) fails with negative edges — a locally non-optimal edge might lead to a globally shorter path via a negative shortcut. Use Bellman-Ford (DP) instead.
Greedy vs DP Decision Framework
Try greedy first: sort by a key and scan once
If the problem has a natural ordering (by end time, by ratio, by deadline), try greedy. Test it on 2–3 examples including edge cases. If it holds, state the invariant and move on.
Fall back to DP: when a past choice can be undone for benefit
If choosing greedily at step i might prevent a better choice at step j > i, you need DP. The coin change counterexample shows this — picking 4 too early blocks the optimal 3+3 path.
The key question: is there ever a reason to defer a greedy choice?
Interval scheduling: no — picking earliest-end-time now never hurts later. Jump Game: no — maximizing reach now is always at least as good. Knapsack: yes — skipping a heavy item now might allow two lighter items later.