Greedy Algorithms
Picture paying for a snack with the fewest coins possible: you probably grab the biggest coin that still fits, then the next biggest, and so on, without ever going back to reconsider an earlier coin. That's a greedy algorithm: make the locally best choice at every step and never look back. No recursion tree, no backtracking, no undo. That makes greedy algorithms fast, usually O(n log n) or better, but the entire interview is about proving the greedy choice is actually safe. For every problem where greedy works, there's a near-identical variant where it silently gives a wrong answer.
Greedy choice property
A problem has the greedy choice property if a locally best choice at every step leads to a globally best solution, and, critically, making that choice never rules out reaching the true best answer. This needs to be proven, not assumed. The standard way to convince yourself, and an interviewer, is an exchange argument: take a best solution that didn't make the greedy choice, show you can swap it in without making the solution worse, and that proves the greedy choice was at least as good.
Example: Jump Game II (minimum jumps to reach the end). The greedy rule, at each step jump to whichever reachable position stretches your reach the furthest, rather than the position closest to the end, works because reach is transitive: whatever the furthest-reaching position can eventually access, every other reachable position can access too, or less. You lose nothing by maximizing reach at every step.
# Greedy choice property check, informally:
# 1. State the greedy rule in one sentence.
# 2. Ask: does an optimal solution exist that makes a DIFFERENT choice here
# and still does at least as well? If yes, greedy is wrong.
# 3. If no such solution exists, the greedy choice is safe.Remember: a greedy choice is only safe if you can prove no better solution ever needs to undo it. If you can't state that proof in a sentence, don't trust the greedy rule yet.
Local vs global optimum
Greedy's failure mode is a locally attractive choice that quietly closes off a better path later. Classic counterexample: coin change with denominations [1, 3, 4] and target 6. Greedy picks the largest coin that's <= the remaining amount every time: 4 + 1 + 1 = 3 coins. The true best answer is 3 + 3 = 2 coins. Greedy's "take the biggest coin now" was locally sensible but globally wrong. This is exactly why coin change in general needs DP, not greedy; greedy only works for specific denomination sets, like US currency.
The interview skill is recognizing which category a new problem falls into before committing to an approach. If you can't build a proof or a clean exchange argument in under a minute, that's your signal to fall back to DP or search instead of forcing greedy.
Remember: a choice that looks best right now can quietly block the actual best path later. Coins
[1,3,4], target 6, is the go-to counterexample to test any new greedy idea against.
When greedy fails
Signs a problem is not greedy-safe:
- The "obviously best" local choice depends on information you don't have yet (later constraints change what "best" even means).
- A counterexample is easy to build by hand; always try 2-3 small cases before committing to greedy.
- The problem asks for a count of all ways, or needs backtracking over choices: greedy produces one answer, not an exploration of alternatives.
If you can't rule these out quickly, say so out loud in the interview and default to DP. Proposing greedy and then getting handed the counterexample mid-interview is a worse outcome than never proposing it at all.
Remember: if you can build a counterexample in under a minute, greedy is wrong for this problem. Test small cases before you commit.
Jump Game
LeetCode 55 · Jump Game · Greedy · Forward traversal
Intuition: Track the furthest index reachable so far. If you ever reach an index beyond that furthest-reachable point before updating it, you're stuck. Otherwise, by the time you reach the last index, it was always within reach.
Approach: Single forward pass; maintain max_reach. At each index i, if i > max_reach the current index is unreachable, so fail immediately. Otherwise update max_reach = max(max_reach, i + nums[i]).
def can_jump(nums: list[int]) -> bool:
max_reach = 0
for i, num in enumerate(nums):
if i > max_reach:
return False # can't even reach this index
max_reach = max(max_reach, i + num)
if max_reach >= len(nums) - 1:
return True
return TrueComplexity: O(n) time, O(1) space.
Common mistakes: checking max_reach >= len(nums) - 1 only after the loop instead of inside it. That's still correct but misses an early-exit optimization. Also, using DP with O(n²) reachability checks when the greedy one-pass version is strictly simpler and faster.
Remember: track the furthest reach seen so far. If the index you're standing on is ever past that reach, you were never going to make it.
Jump Game II
LeetCode 45 · Jump Game II · Greedy · Minimum jumps
Intuition: Think in "levels," like BFS on an implicit graph. current_end marks the boundary of the current jump's reach; farthest tracks the best reach achievable from any position within the current level. When you hit current_end, you're forced to take another jump: increment the counter and advance the boundary to farthest.
Approach: This is the "maximize reach at every step" greedy choice from earlier in this lesson, formalized into a BFS-level counter.
def jump(nums: list[int]) -> int:
jumps = 0
current_end = 0
farthest = 0
for i in range(len(nums) - 1): # don't need to jump from the last index
farthest = max(farthest, i + nums[i])
if i == current_end:
jumps += 1
current_end = farthest
return jumpsComplexity: O(n) time, O(1) space.
Common mistakes: confusing this with Jump Game I. This problem counts minimum jumps, not reachability, and the greedy rule here, maximize reach, advance the boundary only when forced, is different from a plain reachability scan. Also, looping through the entire array including the last index, an off-by-one, since you never need to jump from the destination.
Remember: advance the jump counter only when you're forced to, when you've hit the boundary of what the current jump could reach.
Meeting Rooms II
LeetCode 253 · Meeting Rooms II · Greedy · Min heap
Intuition: The number of rooms needed at any instant equals the number of meetings currently overlapping. Sort meetings by start time, then use a min-heap of end times to track which room frees up soonest. If the earliest-ending meeting has already finished by the time the next meeting starts, reuse that room instead of allocating a new one.
Approach: Sort by start. Keep a min-heap of currently occupied rooms' end times. For each meeting, pop and reuse if the heap's smallest end time is <= the new meeting's start; otherwise push a new end time (a new room). The heap's final size is the answer.
import heapq
def min_meeting_rooms(intervals: list[list[int]]) -> int:
if not intervals:
return 0
intervals.sort(key=lambda pair: pair[0])
heap = [] # min-heap of end times of currently occupied rooms
for start, end in intervals:
if heap and heap[0] <= start:
heapq.heappop(heap) # reuse the room that just freed up
heapq.heappush(heap, end)
return len(heap)Complexity: O(n log n) time (sort plus n heap operations), O(n) space for the heap.
Common mistakes: forgetting to sort by start time first, since the greedy reuse logic assumes meetings arrive in chronological order. Also, using < instead of <= when comparing an end time to a start time: a meeting ending exactly when another starts can share a room, assuming the problem's convention allows it, so confirm that with the interviewer.
Remember: the heap's smallest end time tells you the soonest a room frees up. Reuse it if that room is free by the time the next meeting starts.
Task Scheduler
LeetCode 621 · Task Scheduler · Greedy · Formula
Intuition: The bottleneck is the most frequent task, since it needs n idle slots between each repetition. Build the schedule around the max-frequency task(s): (max_freq - 1) full cooldown blocks of size (n + 1), plus however many tasks tie for the max frequency in the final block. Anything beyond that fills the idle slots for free.
Approach: Compute frequency counts, find max_freq and how many tasks are tied at max_freq. The formula: max(len(tasks), (max_freq - 1) * (n + 1) + count_of_max_freq_tasks).
from collections import Counter
def least_interval(tasks: list[str], n: int) -> int:
counts = Counter(tasks)
max_freq = max(counts.values())
num_max = sum(1 for count in counts.values() if count == max_freq)
# (max_freq - 1) full blocks of size (n + 1), plus the final partial block
formula = (max_freq - 1) * (n + 1) + num_max
return max(len(tasks), formula)Complexity: O(k) time where k is the number of tasks (counting) plus O(26) for the frequency scan, effectively O(k). O(1) space (bounded by 26 uppercase letters).
Common mistakes: forgetting max(len(tasks), formula). When there are enough distinct tasks to fill every idle slot, the formula alone can undercount and give a value smaller than the task count itself. Also, miscounting num_max: you must count all tasks tied at the max frequency, not just one of them.
Remember: the most frequent task sets the pace. Everything else either fills its forced idle slots or, if there's enough variety, doesn't need idle slots at all.