cf.completefrontend
GREEDY & INTERVALS · FOUNDATION

Greedy choice

Build the answer one step at a time by always taking the option that looks best right now, when you can prove that never hurts later.

Time O(n log n)Space O(n)22 practice problemsStep-through picture

The idea

A greedy algorithm makes a series of choices, and at each step it picks the option that looks best at that moment: the cheapest item, the earliest deadline, the biggest coin. It never goes back to change a choice.

That sounds too simple to be right, and often it is wrong. Greedy only works for problems where the best-looking choice now is always part of some best final answer. You show this with an exchange argument: take any best answer that made a different choice, swap in the greedy choice, and show the answer doesn't get worse.

When greedy works, it's usually very fast: sort the options once (O(n log n)), then make one pass. When it doesn't work, the usual fix is dynamic programming, which tries every choice instead of just one.

An everyday example

Filling a shopping bag with a fixed amount of cash

You have 20 dollars and want to leave the shop with as many items as possible; which items doesn't matter. You don't need to try every mix of items. You pick up the cheapest item, then the next cheapest, and so on, until the next one would cost more than you have left. Any other mix of the same size would cost at least as much, so cheapest-first always gets the most items.

How the example maps to the code
In the exampleIn the code
Lining up the items by priceconst sorted = [...prices].sort((a, b) => a - b)
The cash you've spent so farspent
The next item would cost too muchif (spent + price > budget) break
Putting an item in the bagspent += price; count++

From the slow way to greedy choice

  1. The obvious way to find the most items a budget can buy is to try every group of items. With n items there are 2^n groups: 64 groups for 6 items, but over a million for 20 items. For each group you add up the prices and compare the total with the budget. That is correct, and far too slow.
  2. Look at what the question really asks. It asks how many items, not which ones. Two groups of the same size are equally good, so for each size m you only need to know whether some group of m items fits. The group of size m most likely to fit is the cheapest one: the m cheapest items.
  3. So you never need to look at any other group. Sort the prices from low to high. The cheapest group of size 1 is the first price, the cheapest group of size 2 is the first two prices, and so on. Each group is the one before it plus one more item, so a running total spent replaces adding up every group from scratch.
  4. Keep adding the next price while the total stays within the budget. The first time it doesn't, stop: every later item costs at least as much, so no bigger group fits either. That loop is the greedy choice: at each step take the option that looks best right now, the cheapest item left, and never undo it.

How it works

  1. Decide the greedy rule: which option looks best at each step. Here: the cheapest item.
  2. Sort the options so the best one comes first: sorted is the prices from cheapest to most expensive.
  3. Walk through sorted. For each price, check if taking it still fits: spent + price <= budget.
  4. If it fits, take it: add it to spent and add one to count.
  5. If it doesn't fit, stop. Every later item costs at least as much, so none of them fit either.
  6. Return count.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function mostItems(prices, budget) {
  2. const sorted = [...prices].sort((a, b) => a - b);
  3. let count = 0;
  4. let spent = 0;
  5. for (const price of sorted) {
  6. if (spent + price > budget) break;
  7. spent += price;
  8. count++;
  9. }
  10. return count;
  11. }

How fast it is

TimeO(n log n)
Extra memoryO(n)

Sorting takes O(n log n) and the loop looks at each item at most once. The sorted copy uses O(n) memory.

  • Best caseO(n)

    The prices are already sorted. JavaScript engines such as V8 sort with TimSort, which notices a sorted list in one pass, and the loop is at most one more pass.

  • Average caseO(n log n)

    Prices in random order: the sort does about n log₂ n comparisons, and the loop adds at most n steps.

  • Worst caseO(n log n)

    Every item fits, so the loop visits all n items after a full sort. The sort is still the biggest cost.

Common mistakes

  • Trusting a greedy rule without checking it. Try small examples, including tricky ones, or write a brute force to compare against.
  • Sorting by the wrong key. For example, sorting meetings by start time instead of end time gives wrong answers for "most meetings".
  • Calling sort() without a compare function on numbers, which sorts them as text: [10, 9, 1] becomes [1, 10, 9].
  • Using greedy when choices affect each other later, like coins of 1, 3, and 4. Those problems need dynamic programming.

When to use it

Look for these clues in a problem:

  • The question asks for the most, the fewest, the cheapest, or the largest of something, and choices don't depend on each other in complicated ways.
  • Sorting by one key (price, deadline, size, end time) seems to make the right choice obvious.
  • A small example can't break the simple rule: try to find a case where the obvious choice loses. If you can't, look for an exchange argument.
  • The input is large, so trying every combination (or a dynamic programming table) would be too slow.

Check yourself

Answer each one in your head first, then open it.

Why can the loop break instead of continue when an item doesn't fit?

The list is sorted, so every later item costs at least as much as the one that didn't fit. If this one is too expensive, all the rest are too.

What breaks if you sort with prices.sort() and no compare function?

It sorts numbers as text, so [10, 9, 2] becomes [10, 2, 9]. The loop may then stop at 10 before trying the cheaper items and return too small a count.

With prices = [5, 5, 5] and budget = 14, what is returned, and how many times does the loop body run?

It returns 2. The body runs three times: two buys, then the third 5 gives 15 > 14 and the loop breaks.

How many groups would the brute force check for 30 items?

2^30, a bit over a billion. Greedy looks at each of the 30 items at most once after one sort.

Does cheapest-first still give the right answer if one item is worth far more than the others?

It still gives the most items, because the question only counts items. It doesn't give the most value: once values matter, the problem becomes a knapsack and needs dynamic programming.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 22 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The rule the loop keeps: after it buys count items, they are the count cheapest items, so spent is the smallest possible cost of any group of that size. That is true at the start, with no items and spent = 0. Each step adds the cheapest item not yet bought, so the rule stays true.

The exchange argument says the same thing from the other side. Take any best answer with m items. If it holds an item that greedy didn't buy while leaving out a cheaper item that greedy did buy, swap the two. The total goes down or stays the same, so the group still fits and still has m items. After enough swaps, the best answer is exactly the m cheapest items, which is what greedy buys.

The loop ends either when it runs out of items or when one doesn't fit. In the second case, the count + 1 cheapest items cost more than budget, and every other group of that size costs at least as much, so no answer has more than count items. The rule plus that ending prove count is the best possible.

Going deeper

3 more ideas

Why cheapest-first can't be beaten

Say the best answer buys m items. The m cheapest items cost no more than any other m items, so if any m items fit the budget, the m cheapest fit too. Greedy buys the cheapest items in order until one doesn't fit, so it buys at least m. This is the exchange argument in its simplest form: swapping any chosen item for a cheaper unchosen one never hurts.

When greedy gives the wrong answer

Making change for 6 cents with coins of 1, 3, and 4 cents: greedy takes the biggest coin first, 4, then 1 and 1, for 3 coins. But 3 + 3 uses only 2 coins. The biggest-coin rule has no exchange argument for these coins, so the problem needs dynamic programming. Always test the rule on small cases before trusting it.

Why it usually takes O(n log n) time

Most greedy algorithms sort once, which costs O(n log n), then make one pass over the sorted options, O(n). Some use a heap instead of sorting when new options appear as the algorithm runs, which also gives O(n log n).

Work it by hand

Every step in a table, with why

Buy as many items as possible with 16 to spend. Two items cost the same, and the fourth item uses up the budget exactly.

prices = [7, 4, 11, 2, 6, 4], budget = 16

Steppricespent + pricespentcountWhat happensWhy
1--00sort: [2, 4, 4, 6, 7, 11]The copy is sorted from cheapest to most expensive. Nothing is bought yet.
222212 <= 16: buy itThe cheapest item fits easily.
346626 <= 16: buy itThe next cheapest item also fits.
441010310 <= 16: buy itThis 4 ties with the one before it. The order of equal prices doesn't matter, because either copy costs the same.
561616416 <= 16: buy itThe total equals the budget exactly. The test is spent + price > budget, so an exact fit still counts as fitting.
672316423 > 16: break7 doesn't fit. 11 costs even more, so the loop stops without looking at it.

It returns 4: the items that cost 2, 4, 4, and 6. No group of 5 items fits, because even the five cheapest cost 23. The loop never had to look at 11.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Greedy choiceO(n log n)O(n)An exchange argument shows the best-looking option is always safe to take, as with cheapest-first for the most items.
Dynamic programming over the budgetO(n · budget)O(budget)Choices affect each other, like items with different values or coins of 1, 3, and 4. It is correct where greedy isn't, but slow when the budget is large.
Try every groupO(2^n)O(n)Only for tiny inputs, or as a brute force to test a greedy rule against on random small cases.
Min-heap, then popO(n + k log n)O(n)Only a few of many items will be taken, or options arrive over time.

Extra memory: O(n) for the sorted copy. Sorting prices in place would save the copy but change the caller's array. The loop itself uses two numbers, spent and count.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Greedy choice and the other approaches, on a scale where each line up is 10 times more steps.
  • Greedy choice O(n log n)
  • Dynamic programming over the budget O(n · budget)
  • Try every group O(2^n)
  • Min-heap, then pop O(n + k log n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Greedy choice339,96620 million
Dynamic programming over the budget1001 million1 trillion
Try every group1,024more than a quadrillionmore than a quadrillion
Min-heap, then pop4310,96621 million

Inputs that need care

5 tricky inputs
No items: prices = []
The loop body never runs and it returns 0. No special check is needed.
Every price is over the budget: prices = [5, 9], budget = 3
The first price already gives 5 > 3, so the loop breaks at once and returns 0.
Free items: prices = [0, 0, 5], budget = 4
The two zeros sort first and always fit, so it returns 2. If free items shouldn't count, filter them out first.
A negative price, like a coupon: prices = [-3, 4, 6], budget = 5
The proof still holds, because the m cheapest items are still the cheapest group of size m. It returns 2: -3 and 4. Check whether the problem really allows negative prices.
Prices read from a form as text: prices = ["10", "9"], budget = 25
The sort turns them into numbers with a - b, but spent + price joins text: 0 + "9" is "09", then "0910". It returns 1 instead of 2. Convert with Number before calling it.

Variations and follow-ups

Twists interviewers add

Most value instead of most items

If each item has a value and you want the most total value within the budget, cheapest-first fails, and so does best-value-per-dollar first when items can't be split. That is the 0/1 knapsack problem, and it needs dynamic programming. If items can be split, like buying part of a bag of rice, best value per dollar first is correct again.

A heap instead of a full sort

If only a few items will fit in a huge list, build a min-heap in O(n) and pop the cheapest items until one doesn't fit. That costs O(n + k log n) for k items bought, which beats a full sort when k is small. A heap is also the right tool when new options appear while the algorithm runs.

Fewest items to reach a target

The mirror question asks for the fewest items whose total is at least target. Sort from most expensive to cheapest and take items until the total reaches the target. The same exchange argument works: the m most expensive items have the biggest total of any m items.

Matching two sorted lists

Some greedy problems pair items from two lists, like giving each child the smallest snack that satisfies them. Sort both lists and walk them with two pointers, always using the smallest option that works. A bigger option is never more useful now than a smaller one that also works, so using the smallest one first is safe.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it when the question asks for the most or the fewest of something, and sorting by one key seems to settle every choice: cheapest, shortest, earliest deadline. A limit like n up to 10^5 also hints that an O(n log n) answer is expected.
  • Before coding, say the rule and why it's safe in one sentence: "I buy the cheapest item first, because swapping any bought item for a cheaper one never makes the group cost more." Interviewers listen for that exchange argument, not just the code.
  • Try to break your own rule out loud with a tiny case. For coins 1, 3, 4 and amount 6, biggest-first gives 3 coins, but 3 + 3 uses 2. Showing that you checked is what separates a proven greedy rule from a lucky one.
  • Test by hand: an empty list, a budget smaller than every price, and a budget that every item fits into exactly. The usual follow-up is "what if items have values?": that is the 0/1 knapsack, solved with dynamic programming in O(n · budget) time.

Where frontend code uses it

The same idea in real UI code
  • Text wrapping in a simple layout fills each line with as many words as fit before breaking, which is a greedy choice. CSS line breaking in browsers is greedy by default (text-wrap: pretty asks for a smarter, non-greedy layout).
  • A responsive toolbar shows as many buttons as fit and moves the rest into an overflow menu, filling space greedily in priority order.
  • Bundlers that split code into chunks under a size limit often add modules greedily until the next one would push the chunk over.

Related algorithms