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
- Greedy builds an answer one locally optimal choice at a time and never backtracks.
- The real work is the justification — an exchange argument or case check that the local best is globally safe.
- Sorting by value density and taking from the top maximizes worth under a capacity limit.
- When only a few values could be the answer, enumerate and test those candidates directly.
- Once the ordering is trusted, greedy solutions are short, fast, and usually one pass after a sort.
Maximum Units on a Truck
Core idea: You have a single truck that holds at most
truckSizeboxes, and box types that differ in how many units each box carries. To squeeze out the most units, you only ever want to spend a box-slot on the richest box available — the one with the highest units-per-box. So sort the box types byunitsPerBoxdescending, then greedily fill the truck from that order: take as many of the densest type as fit, then as many of the next, and so on, stopping the instant the truck is full. There is no weight, no price, no trade-off — every box costs exactly one slot, so a slot is always best spent on the densest box. That single observation makes the greedy provably optimal in O(n log n).
The problem, rephrased
You are the loader at a shipping dock. A clipboard lists the pallets waiting outside, grouped by type: each entry says "there are this many boxes of this type, and each one holds this many units." Your truck can physically fit only a fixed number of boxes — call it truckSize — regardless of what's inside them. Every box, fat or thin, takes up exactly one of those slots. Load the truck so the total number of units driven away is as large as possible, and return that number.
This is LeetCode 1710 — Maximum Units on a Truck.
| Input | Means | Output |
|---|---|---|
boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4 |
1 box×3u, 2 boxes×2u, 3 boxes×1u; fit 4 boxes | 8 |
boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10 |
four types; fit 10 boxes | 91 |
boxTypes = [[3,8]], truckSize = 10 |
one type, 3 boxes×8u; truck holds more than exists | 24 |
Each boxTypes[i] = [count, unitsPerBox]. The cap is on boxes, but you are scored on units — that mismatch is the whole game.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson