Search the Answer
What is this?
This is the clever leap that surprises everyone: instead of searching through your data, you search through the possible answers. Picture asking "could I finish in 5 hours?" — if no, you clearly need more time, and if yes, you wonder whether even less would do. Because "is this much enough?" only ever flips from no to yes once as you allow more, you can guess-and-halve your way to the smallest amount that works, even when the answer is a speed, a capacity, or an amount of time rather than a spot in a list.
💡 Fun fact: "Search the answer" is exactly how engineers size real systems — to find the smallest server fleet that keeps a website fast, you binary-search the count by repeatedly load-testing a guess, instead of trying every possible number one by one.
🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: When a problem asks for the smallest (or largest) value that satisfies some condition, you do not search an array at all — you binary-search the range of possible answers. If "does answer
xwork?" flips from no to yes exactly once asxgrows, that monotonic boundary is exactly what binary search finds, turning a huge answer space into O(log range) feasibility checks.
The pattern
This is the most powerful idea in the chapter: binary search on the answer. Instead of looking for a position, you guess a candidate answer and ask a yes/no feasibility question — and the cost of that single guess is usually a quick O(n) pass.
It works only when feasibility is monotonic: once some value is good enough, every larger (or every smaller) value is too. That gives a clean threshold to home in on. The recipe is always the same. First, identify the answer and its bounds — a lo that is obviously too small and a hi that obviously works. Second, write feasible(x): given candidate x, can the task be done? Third, binary-search for the boundary, biasing toward the smallest x that is feasible (or the largest, depending on the ask).
The skill is recognising the shape: "minimum capacity," "minimum speed," "minimum time," "maximum size that fits" all hide a monotonic feasibility test behind them.
The problems
Koko Eating Bananas — find the slowest eating speed that clears all piles within h hours. Faster is always feasible, so it is monotonic. Check feasibility of a min speed: for candidate speed k, sum the hours needed and test against h; binary-search the smallest k that fits.
Capacity To Ship Packages Within D Days — find the smallest ship capacity that delivers everything in D days. Check feasibility of a min capacity: greedily pack days under capacity c, count days used, and search for the smallest c needing at most D days. lo is the largest single package, hi is the total.
Minimum Time to Complete Trips — find the least total time for buses to finish a quota of trips. Count trips at a time budget: at candidate time t, each bus does t / time[i] trips; sum them and search for the smallest t meeting the quota.
Arranging Coins — find how many full rows a staircase of n coins can form. The answer is the largest k with k(k+1)/2 ≤ n — a triangular number threshold you binary-search directly.
Key takeaways
- Binary-search the answer, not an array. When you want the smallest/largest value that works, the answer space is your search range.
- Feasibility must be monotonic. "Good" values must form one contiguous side; otherwise binary search cannot bracket them.
- Each guess costs one O(n) check. Total cost is O(n log range) — usually a massive win over brute force.
- Set bounds deliberately. A
lothat is too small and ahithat always works keep the loop correct and the boundary inside. - Why this chapter matters: "search the answer" reframes optimization as search, and it is one of the most common and highest-leverage interview patterns.
Core idea: Don't search the data — search the answer. The speed you can pick is a sorted range, "fast enough?" is monotonic, so binary-search the smallest speed that works.
Problem, rephrased
You run a tiny overnight batch job. There are several queues of tasks waiting, and you have a fixed number of hours before the morning deadline. Your worker drains tasks at a single, constant speed k (tasks per hour) that you must commit to up front.
There's one quirk: the worker only touches one queue per hour. In a given hour it pulls up to k tasks from a single queue. If fewer than k tasks remain in that queue, it clears them and then sits idle for the rest of the hour — it does not roll over to start another queue. So a queue of size p always costs ceil(p / k) whole hours, no matter what the other queues look like.
You want the worker to relax — pick the smallest integer speed k that still finishes every queue within h hours.
Concretely: given piles (queue sizes) and h (hours available), at speed k queue i takes ceil(piles[i] / k) hours. Find the minimum integer k such that the total hours is <= h.
piles (queue sizes) |
h (hours) |
Answer k (min speed) |
Why |
|---|---|---|---|
[4, 8, 3] |
6 |
3 |
At k=3: ceil(4/3)+ceil(8/3)+ceil(3/3) = 2+3+1 = 6 ≤ 6 ✓ |
[12, 5, 9] |
4 |
9 |
At k=9: ceil(12/9)+ceil(5/9)+ceil(9/9) = 2+1+1 = 4 ≤ 4 ✓ |
[7, 7, 7, 7] |
10 |
4 |
At k=4: 4 × ceil(7/4) = 4 × 2 = 8 ≤ 10 ✓ |
In each row, one less speed pushes you over h — that's what makes the answer the minimum.
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