Greedy Choice

What is this?

A greedy choice means picking what looks best right this second and never taking it back, the way you hand over the biggest coins first when making change. The catch is that grabbing the best-looking option does not always lead to the best overall result, so the real work here is convincing yourself that the local pick is safe. Once you trust the order to pick things in, the actual solving is a quick single pass.

💡 Fun fact: Sometimes only a handful of values can possibly be the answer, so trying every candidate is still fast. For the domino puzzle here, the winning value must appear on the very first domino, which leaves just two options to check out of all the possibilities.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: a greedy algorithm builds an answer by repeatedly taking the choice that looks best right now and never reconsidering it. The whole challenge is justifying that the local best is also globally safe — once you trust the ordering, the solution is a short, fast scan.

The pattern

Each problem here picks a clear notion of "best next move" and commits to it. The supporting argument is an exchange or case analysis showing the greedy choice loses nothing.

• Sort by value density, then take. When you have a capacity to fill with items of differing worth, rank items by worth per unit and take from the top until full. Any swap toward a lower-density item can only reduce the total, so the greedy order is optimal.
• Try the few candidate targets. When the goal is to make everything equal and only a handful of values could possibly work, enumerate those candidates explicitly, test each for feasibility, and take the cheapest. The candidate set is tiny, so trying all of them is cheap and exhaustive.

The common thread: define the local criterion, argue it is safe, and let a single pass (after an optional sort) finish the job.

The problems

Maximum Units on a Truck — each box type carries a number of units; the truck holds a fixed number of boxes. Sort box types by units per box descending, then load greedily from the densest type until the truck is full. Trading any loaded box for a lower-unit one only loses units, so the sort order is optimal.

Minimum Domino Rotations for Equal Row — to make one row of a domino pair all identical, the common value must be either the top or the bottom of the first domino — only two candidates. For each candidate, check that every domino can show it on the chosen row, count the rotations needed for top and bottom, and keep the minimum; if neither candidate is feasible, it is impossible.

Key takeaways

1. Greedy builds an answer one locally optimal choice at a time and never backtracks.
2. The real work is the justification — an exchange argument or case check that the local best is globally safe.
3. Sorting by value density and taking from the top maximizes worth under a capacity limit.
4. When only a few values could be the answer, enumerate and test those candidates directly.
5. Once the ordering is trusted, greedy solutions are short, fast, and usually one pass after a sort.