Greedy Algorithms

1The mental model (what this really is)#

A greedy algorithm builds an answer one step at a time. The shape is always the same:

• Look at the choices in front of you, pick the one that looks best by a fixed rule.
• Commit to it. No "let me reconsider that decision from five steps ago."
• Move on. Each frozen choice stacks up into the final answer.

The mental picture I use: someone hands you backpack items one at a time, and you decide each one the instant you see it.

• If the rule is right, decisions stack into a beautifully simple solution.
• If the rule is wrong, greedy quietly returns something plausible but wrong, which is the dangerous failure mode.
• A wrong greedy often passes the sample test and dies on the one case the interviewer picked on purpose.

Greedy versus DP, the contrast that makes it click:

• DP keeps every option alive and reconciles them at the end. Safe, but slow and memory-hungry.
• Greedy throws options away the instant it decides. Fast and cheap, but only correct when throwing them away can never hurt you.
• Same currency, opposite bet: DP buys safety with time and space, greedy buys speed by betting the local choice is enough.

2How to recognize it (the signals in a problem)#

You will never be told "use greedy." You have to smell it. Here are the signals I trust, roughly in order of how strongly they fire.

• It asks for a max, min, or count and feels optimization-shaped. "Maximum meetings," "minimum coins," "fewest platforms." Optimization is the entry ticket. "Number of ways" or "is it possible" is a different animal (usually DP or BFS).
• There is a natural ordering that makes one choice obviously better. Soonest finish time, smallest coin, highest value-to-weight ratio. When sorting by some key makes a choice feel forced, that is greedy whispering.
• A local choice does not block future choices (the big one). If grabbing the best option now never paints you into a corner later, greedy usually holds. Ask yourself: "If I grab this now, can it ever cost me more than it gains me down the line?"
• The answer is a pile of independent-ish decisions. Intervals kept or dropped, jumps taken, characters placed. Each decision is small and self-contained.

The counter-signal (the thing that says "not greedy"):

• A choice now changes the value of future choices in a tangled way, so you would need to explore combinations to be sure.
• Coin change with weird denominations is the classic trap. For coins {1, 3, 4} making 6, greedy-by-biggest grabs 4, then 1, then 1 (three coins), but optimal is 3 + 3 (two coins).
• That is a DP problem wearing a greedy costume, and interviewers love it precisely because the greedy answer looks reasonable.

3The template (how it works, with pseudocode)#

Almost every greedy solution has the same bones:

1. Figure out the greedy choice: the single rule for "best right now."
2. Sort or heap the input so that best choice is cheap to grab.
3. Walk the elements in that order.
4. For each element, either take it or skip it based on the rule.
5. Track whatever state the rule needs (last end time, current reach, running total).
6. Return the accumulated answer.

In code it usually looks like this:

def greedy(items):
    items.sort(key=choice_key)   # the ordering that makes greedy valid
    result = 0
    state = initial_state
    for item in items:
        if can_take(item, state):
            result += 1          # or += item.value, etc.
            state = update(state, item)
    return result

Two lines carry all the weight:

• choice_key: how you sort. This is the brain of the solution.
• can_take: the rule for take-or-skip. Usually trivial once the sort is right.
• Picking the wrong sort key is the single most common way people write confident, wrong greedy code. Strong candidates sort scheduling by start time instead of end time and then burn five minutes confused about an off-by-one answer.

On proving it (interviewers always ask "why does this work?"):

• The standard tool is the exchange argument. Assume some optimal answer exists. Show that if it differs from your greedy choice, you can swap in the greedy choice without making things worse.
• If every greedy pick can be swapped in safely, greedy is at least as good as optimal, so it is optimal.
• You do not need a formal proof in the room. You need one clean sentence showing the swap is safe, delivered before or while you code. That sentence often separates a "yes" from a "maybe" on the feedback form.

The sort is the brain. The loop is the hands.

4A worked example (walk through one problem step by step)#

Interval scheduling, because it teaches the right instinct and shows up under five different names across companies.

Problem: You are given a set of meetings, each with a start and end time. You can attend only one meeting at a time. What is the maximum number of meetings you can attend?

The meetings: A(1,3), B(2,5), C(4,7), D(6,8), E(5,9)

Feel the tempting-but-wrong instincts first. Interviewers dangle these on purpose.

• Pick the shortest meetings first? Sounds efficient. But a short meeting sitting mid-day can block two others that would have fit around it. Picture a 30-minute meeting at noon straddling the only two 2-hour slots you had. You trade two meetings for one. No.
• Pick the earliest starts? You grab A(1,3), good, but next is B(2,5), which overlaps A anyway. An early start that runs late is strictly worse than a later start that ends sooner. No.

The choice that actually works: pick the meeting that finishes earliest.

• Finishing early leaves the most room for everything after it.
• Free yourself as soon as possible and you maximize what is still reachable.
• Not obvious until you see it. Once you see it, every interval variant becomes the same problem.

Sort by end time: A(1,3), B(2,5), C(4,7), D(6,8), E(5,9) (A ends 3, B ends 5, C ends 7, D ends 8, E ends 9.)

Walk it, tracking last_end (the time I am free again). Start last_end = -infinity, count = 0.

• A(1,3): starts at 1, I am free (1 >= -inf). Take it. count = 1, last_end = 3.
• B(2,5): starts at 2, busy until 3. 2 < 3, overlap. Skip.
• C(4,7): starts at 4, free at 3. 4 >= 3. Take it. count = 2, last_end = 7.
• D(6,8): starts at 6, busy until 7. Overlap. Skip.
• E(5,9): starts at 5, busy until 7. Overlap. Skip.

Answer: 2 meetings (A and C).

What to notice:

• The decision rule in the loop was dead simple: if meeting.start >= last_end: take it.
• All the intelligence lived in the sort. That is the shape of most greedy solutions.
• The exchange argument, one line: if some optimal schedule did not use the earliest-finishing meeting, swap its first meeting for the earliest-finishing one. The swap cannot cause a conflict (you freed up at least as early) and does not lose a meeting, so optimal stays optimal. Greedy matches it.
• Say exactly that sentence in the room and you have answered "why does this work" before they finish asking.

Complexity: O(n log n) for the sort, O(n) for the walk. Space O(1) beyond the input (O(n) if the language's sort allocates, so say "in-place sort" if you want to claim O(1)).

5Variations and gotchas#

The core pattern flexes into several shapes you will see again and again. Learn the shapes, not the individual problems, and new problems stop being new.

• Sort by the right key. Interval scheduling sorts by end. Merging intervals sorts by start. Min-platforms and meeting-rooms split starts and ends into two sorted streams and sweep. Always ask: what ordering makes my local choice safe? "Sort by start or end?" answers itself once you name what you are optimizing.
• Heap-based greedy. When "best right now" changes as you consume elements, a sorted array is not enough. Use a priority queue so the current best is always on top. Think connect ropes with minimum cost (always merge the two shortest) or task scheduling with cooldowns. Same spirit, still O(n log n) from n push/pop operations.
• Two-pointer greedy. Some problems let you move pointers from both ends. Max water container, assign cookies. You advance the side whose move cannot hurt: in the container problem, move the shorter wall, because it is the binding constraint and moving the taller one only shrinks width without lifting the ceiling.
• Greedy with a running frontier. Jump Game and its cousins track "farthest I can currently reach" and extend it as you walk. No sort, so O(n). The greedy choice is implicit: refresh max_reach at each index, and if your current index ever passes max_reach, you are stuck.

Gotchas that bite people:

• Ties. When two elements share the sort key, the tiebreak sometimes matters. In Queue Reconstruction by Height, sorting height descending with count ascending is correct and the reverse is wrong. Decide the tiebreak deliberately, out loud.
• Sorting the wrong field. Reread what you actually optimize before you pick .sort(key=...). Start versus end in intervals is the classic one-character mistake that blows up the answer.
• Assuming greedy without checking. The costliest one. Coin change with arbitrary denominations, 0/1 knapsack (indivisible items), and "max sum with no two adjacent" all look greedy and are not. They need DP. Nuance worth stating: fractional knapsack is greedy (highest value-to-weight ratio first), but 0/1 knapsack is not, because you cannot take a fraction of an item to top off the bag.

6Complexity#

Greedy's whole appeal is speed. The dominant cost is almost always the sort.

• Sort-based: O(n log n) time. The default shape.
• Heap-based: O(n log n) too, from n push/pop operations where each costs O(log n).
• Frontier-style with no sorting: O(n). These are the problems where greedy beats DP most dramatically.
• Space: O(1) or O(n), depending on whether you sort in place or need a heap.

The gap that interviewers are grading:

• Compare to the DP alternative for the same optimization flavor, which often costs O(n) or O(n*target) in both time and space.
• Coin change by DP is O(n*amount). If the amount is a million, that table is enormous, while the greedy version (when the coin system allows it) is a tight O(n log n) with constant extra space.
• When greedy is valid it is typically an order of magnitude simpler and faster than the DP solution. The gap between the two is exactly the gap they are testing you on.

7Mistakes that cost people the round#

• Jumping to greedy without a correctness check. Clean code, passes the example, then "are you sure?" and you fold. Sanity-check with a tiny adversarial case before committing. Thirty seconds of "let me try to break this" buys you the round.
• Using greedy on a DP problem. The signature failure. If choices interact, greedy silently returns a worse answer, no error, no crash, just a wrong number. The interviewer knows the counterexample (often the {1, 3, 4} coin case or a 0/1 knapsack instance). Find it first.
• Picking the wrong greedy rule. Shortest-first versus earliest-finish-first in scheduling. Both feel reasonable, one is wrong. Spend ten seconds justifying the rule out loud before coding, because the rule is 90 percent of the solution.
• Not stating the exchange argument. One sentence ("finishing earliest leaves the most room, so swapping it in never hurts") separates you from someone who memorized the pattern. Senior interviewers weight this heavily, because at staff level they are hiring judgment, not recall.
• Forgetting to sort, or sorting the wrong field. Trivial to fix, embarrassing to debug under pressure. Say your sort key out loud and name why that field, not the other one.
• Overcomplicating the loop. Once the sort is right, the loop is three lines. A sprawling loop with nested conditionals usually means your sort key is wrong and you are compensating in code. Stop and fix the sort.

8Your practice path (named problems by difficulty)#

Do them in this order. Each teaches a distinct flavor, and later ones assume you learned the earlier one.

Warm up (easy):

• Assign Cookies
• Lemonade Change
• Best Time to Buy and Sell Stock II
• Maximum Subarray (Kadane's, a greedy classic)

Core patterns (medium):

• Jump Game
• Jump Game II
• Gas Station
• Non-overlapping Intervals
• Merge Intervals
• Meeting Rooms II
• Task Scheduler
• Partition Labels
• Queue Reconstruction by Height

Earn your stripes (harder):

• Candy
• Minimum Number of Arrows to Burst Balloons
• Reorganize String
• Minimum Number of Refueling Stops
• Course Schedule III
• IPO

How to actually practice these:

• Work them by hand first, before touching code.
• For each, write one sentence stating the greedy choice and why it is safe before coding. If you cannot write that sentence, you do not understand the problem yet.
• Solve 15 of these slowly and be able to prove each one, rather than grinding 50 on autopilot. The interviewer's follow-up is always "why does that work."

9Where this shows up#

Greedy is a staple of phone screens and the first onsite coding round almost everywhere, because it is fast to pose and reveals a lot about how you think.

• Amazon loves interval and scheduling problems, so expect Meeting Rooms II or a non-overlapping-intervals variant on the loop.
• Google and Meta lean toward the "is greedy even valid here?" judgment call, often pairing a greedy problem with a DP lookalike. This is why you will sometimes get coin change and be expected to notice it is not greedy.
• Startups tend to use the classics (Jump Game, Gas Station) as quick 25-minute filters.
• Design-flavored rounds have greedy hearts too: rate limiting, task scheduling, cache eviction (LRU and cousins). Recognizing it there reads as fluency, and fluency reads as seniority.

See the company guides to find which rounds and teams lean hardest on greedy, and pair this with the DP guide so you never confuse the two under pressure.