A greedy algorithm makes the best-looking choice at each step, hoping that locally optimal decisions lead to a globally optimal solution. No going back, no reconsidering. Just pick what looks best right now and move on.
In simple language, it’s like eating at a buffet where we always grab the most delicious item in front of us. Sometimes that strategy works perfectly. Sometimes we end up with five desserts and no actual meal.
When Does Greedy Work?
Greedy works when two conditions hold:
- Greedy choice property — a locally optimal choice leads to a globally optimal solution
- Optimal substructure — an optimal solution contains optimal solutions to subproblems
The tricky part? Not every problem has these properties. That’s why greedy doesn’t always work, and why interviewers love asking us to prove it does.
Activity Selection / Interval Scheduling
This is THE classic greedy problem. Given a list of activities with start and end times, pick the maximum number of non-overlapping activities.
The greedy insight: always pick the activity that ends earliest. This leaves the most room for future activities.
function activitySelection(activities) {
// sort by end time
activities.sort((a, b) => a[1] - b[1]);
const selected = [activities[0]];
let lastEnd = activities[0][1];
for (let i = 1; i < activities.length; i++) {
if (activities[i][0] >= lastEnd) { // no overlap
selected.push(activities[i]);
lastEnd = activities[i][1];
}
}
return selected;
}
// activitySelection([[1,3],[2,5],[3,6],[5,7],[8,9]])
// => [[1,3],[3,6],[8,9]] -- 3 activities, no overlapsdef activity_selection(activities):
# sort by end time
activities.sort(key=lambda x: x[1])
selected = [activities[0]]
last_end = activities[0][1]
for start, end in activities[1:]:
if start >= last_end: # no overlap
selected.append([start, end])
last_end = end
return selected
# activity_selection([[1,3],[2,5],[3,6],[5,7],[8,9]])
# => [[1,3],[3,6],[8,9]] -- 3 activities, no overlapsstatic List<int[]> activitySelection(int[][] activities) {
// sort by end time
Arrays.sort(activities, (a, b) -> a[1] - b[1]);
List<int[]> selected = new ArrayList<>();
selected.add(activities[0]);
int lastEnd = activities[0][1];
for (int i = 1; i < activities.length; i++) {
if (activities[i][0] >= lastEnd) { // no overlap
selected.add(activities[i]);
lastEnd = activities[i][1];
}
}
return selected;
}Time: O(n log n) for sorting. The greedy pass itself is O(n). Space: O(n) for the result.
Jump Game
Given an array where each element tells us the maximum we can jump from that position, determine if we can reach the last index (LeetCode #55).
The greedy insight: track the farthest position we can reach. If we ever land on a position beyond our farthest reach, we’re stuck.
function canJump(nums) {
let farthest = 0;
for (let i = 0; i < nums.length; i++) {
if (i > farthest) return false; // can't reach here
farthest = Math.max(farthest, i + nums[i]);
}
return true;
}
// canJump([2,3,1,1,4]) => true (0->1->4 or 0->2->3->4)
// canJump([3,2,1,0,4]) => false (stuck at index 3)def can_jump(nums):
farthest = 0
for i in range(len(nums)):
if i > farthest:
return False # can't reach here
farthest = max(farthest, i + nums[i])
return True
# can_jump([2,3,1,1,4]) => True
# can_jump([3,2,1,0,4]) => Falsestatic boolean canJump(int[] nums) {
int farthest = 0;
for (int i = 0; i < nums.length; i++) {
if (i > farthest) return false; // can't reach here
farthest = Math.max(farthest, i + nums[i]);
}
return true;
}
// canJump([2,3,1,1,4]) => true
// canJump([3,2,1,0,4]) => falseTime: O(n), Space: O(1). One pass through the array. Beautiful.
Gas Station
There are n gas stations in a circle. Station i has gas[i] fuel and costs cost[i] to reach the next station. Find the starting station that lets us complete the full circuit, or return -1 (LeetCode #134).
The greedy insight: if the total gas >= total cost, a solution must exist. And if we can’t reach station j from station i, then no station between i and j can be the start either. So we reset our start to j+1.
function canCompleteCircuit(gas, cost) {
let totalTank = 0, currTank = 0, start = 0;
for (let i = 0; i < gas.length; i++) {
const diff = gas[i] - cost[i];
totalTank += diff;
currTank += diff;
if (currTank < 0) { // can't reach next station
start = i + 1; // reset start to next station
currTank = 0;
}
}
return totalTank >= 0 ? start : -1;
}def can_complete_circuit(gas, cost):
total_tank = curr_tank = start = 0
for i in range(len(gas)):
diff = gas[i] - cost[i]
total_tank += diff
curr_tank += diff
if curr_tank < 0: # can't reach next station
start = i + 1 # reset start to next station
curr_tank = 0
return start if total_tank >= 0 else -1static int canCompleteCircuit(int[] gas, int[] cost) {
int totalTank = 0, currTank = 0, start = 0;
for (int i = 0; i < gas.length; i++) {
int diff = gas[i] - cost[i];
totalTank += diff;
currTank += diff;
if (currTank < 0) { // can't reach next station
start = i + 1; // reset start to next station
currTank = 0;
}
}
return totalTank >= 0 ? start : -1;
}Time: O(n), Space: O(1). Single pass with two running sums.
Proving Greedy Correctness in Interviews
Interviewers often ask: “How do we know greedy works here?” There are two standard approaches:
1. Exchange Argument
Show that swapping any non-greedy choice with a greedy one never makes the solution worse.
“If our greedy picks activity A (earliest end), and some optimal solution picks activity B instead, we can swap B for A. Since A ends earlier, everything after still fits. So the greedy solution is at least as good.”
2. Greedy Stays Ahead
Show that at every step, the greedy solution is at least as good as any other.
“After picking k activities, greedy’s last end time is <= any other strategy’s last end time. Proof by induction on k.”
In simple language, we don’t need a formal proof in an interview. But we do need to say something like: “The greedy choice never blocks a better option later, because…” and give an intuitive argument. If we can’t articulate why greedy works, we should probably use DP instead.
Common Greedy Problems to Practice
| Problem | Greedy Strategy | Complexity |
|---|---|---|
| Activity Selection | Pick earliest end time | O(n log n) |
| Jump Game | Track farthest reachable | O(n) |
| Gas Station | Reset start when tank < 0 | O(n) |
| Assign Cookies | Sort both, match smallest | O(n log n) |
| Best Time to Buy/Sell Stock | Track min price so far | O(n) |
| Minimum Platforms | Sort arrivals/departures | O(n log n) |
The pattern with greedy: sort the input (usually), then make one pass making the locally best choice. If that gives the right answer, great. If not, we need DP or backtracking.