Binary Search on Answer Space: Hards Feel Like Mediums

If you have ever stared at a LeetCode Hard and thought "this has nothing to do with binary search," you are not alone. Problems like Split Array Largest Sum (#410) and Capacity to Ship Packages Within D Days (#1011) look like dynamic programming or greedy puzzles at first glance. But they all share a secret: binary search on the answer space.

This pattern is the single biggest unlock for intermediate LeetCode grinders. Once you see it, you cannot unsee it. Problems that took 45 minutes of failed DP attempts suddenly collapse into 15-line solutions with clean O(n log k) complexity.

Binary search on the answer space works by flipping the question. Instead of asking "what is the answer?", you ask "is X a valid answer?" Then you binary search over all possible values of X to find the optimal one. The answer space is always bounded and monotonic — if X works, then X+1 works too (or vice versa). That monotonicity is exactly what binary search needs.

Traditional binary search looks for a target value in a sorted array. Binary search on the answer space does something fundamentally different: it searches over the range of possible answers to an optimization problem.

Consider Koko Eating Bananas (#875). Koko has piles of bananas and h hours to eat them all. She picks a speed k (bananas per hour) and eats one pile at a time, taking ceil(pile/k) hours per pile. You need to find the minimum k such that she finishes within h hours.

The key insight is that the answer space — all possible values of k — is monotonic. If Koko can finish at speed 5, she can definitely finish at speed 6, 7, or any higher speed. If she cannot finish at speed 4, she cannot finish at speed 3, 2, or 1 either. This creates a clean boundary: there exists some minimum k where the answer flips from "impossible" to "possible."

That boundary is exactly what binary search finds. You define lo as the smallest possible answer (1 banana per hour) and hi as the largest possible answer (the biggest pile). Then you binary search for the smallest k where Koko can finish in time.

Every binary search on answer space problem follows the same skeleton. The only thing that changes between problems is the feasibility function — the check that tells you whether a candidate answer works.

Here is the template in pseudocode. Define lo and hi as the minimum and maximum possible answers. While lo is less than hi, compute mid as the midpoint. If canAchieve(mid) returns true, set hi to mid (the answer might be even smaller). Otherwise, set lo to mid plus one. When the loop ends, lo equals hi and that is your answer.

The feasibility function canAchieve(mid) is where all the problem-specific logic lives. For Koko Eating Bananas, it checks whether eating at speed mid lets her finish all piles within h hours. For Capacity to Ship Packages, it checks whether capacity mid lets you ship all packages within d days. The function is almost always a simple O(n) greedy scan.

The beauty of binary search on answer space is how many seemingly different problems it solves with the same template. Here are four classics that every interview candidate should know.

Koko Eating Bananas (#875, Medium) is the gentlest introduction. The answer space is [1, max(piles)]. The feasibility check sums ceil(pile/k) for each pile and checks if the total is within h hours. This is the problem to start with — it makes the pattern crystal clear.

Capacity to Ship Packages Within D Days (#1011, Medium) asks for the minimum ship capacity to deliver all packages in d days. The answer space is [max(weights), sum(weights)]. The feasibility check greedily loads packages onto ships: if adding the next package exceeds capacity, start a new day. Count the days and check if you are within d.

Split Array Largest Sum (#410, Hard) asks you to split an array into m subarrays such that the largest subarray sum is minimized. The answer space is [max(nums), sum(nums)]. The feasibility check greedily assigns elements to subarrays: if adding the next element exceeds the candidate maximum sum, start a new subarray. Count subarrays and check if you used at most m.

Magnetic Force Between Two Balls (#1552, Medium) asks for the maximum minimum distance between any two balls placed in positions. Here you maximize instead of minimize, so the binary search logic flips: if canAchieve(mid) is true, set lo to mid plus one. The answer space is [1, max(positions) - min(positions)]. The feasibility check greedily places balls at least mid apart.

The hardest part of this pattern is not writing the code — it is recognizing that binary search applies in the first place. These problems never say "sorted array" or "search." Instead, they hide behind optimization language.

Watch for these trigger phrases in the problem statement: "minimize the maximum," "find the minimum speed such that," "what is the smallest capacity that allows," "maximize the minimum distance," or "find the least X such that Y is satisfied." Any time you see bounded optimization with a monotonic feasibility condition, think binary search on the answer space.

Another strong signal is when brute force would try every possible answer from 1 to some large N. If checking each answer takes O(n) and there are N possible answers, brute force is O(n * N). Binary search on answer space reduces it to O(n * log N) — a massive improvement when N is large.

The binary search wrapper is always the same five lines. The feasibility function is where the real intellectual work happens. Getting it right is the difference between a clean AC and a frustrating WA.

For most problems, the feasibility function is a greedy O(n) scan. You walk through the input left to right, accumulating elements into a "group" (a day, a subarray, a ship load). When adding the next element would violate the constraint (exceed the candidate answer), you start a new group. At the end, you check whether the number of groups is within the allowed limit.

The most common mistake is getting the boundary conditions wrong. For minimize problems, canAchieve(mid) should return true when mid is large enough. For maximize problems, it should return true when mid is small enough. Always test your feasibility function mentally with the smallest and largest possible answers before coding the binary search wrapper.

Time complexity is almost always O(n log(hi - lo)), where n is the input size and (hi - lo) is the answer range. The log factor comes from binary search, and each iteration runs the O(n) feasibility check. Space complexity is O(1) for the binary search and feasibility function itself.

Start with Koko Eating Bananas (#875). It is the purest expression of the pattern with no extra complications. Write the feasibility function from scratch, make sure it passes, and internalize the template.

Next, solve Capacity to Ship Packages (#1011). The feasibility logic is nearly identical to Koko but with a different domain (shipping instead of eating). This repetition is deliberate — you want the template to become muscle memory.

Then tackle Split Array Largest Sum (#410). This is rated Hard, but if you have solved the previous two, you will notice it is the exact same template with a slightly different feasibility check. The jump from Medium to Hard is purely about recognition, not difficulty.

For a bonus challenge, try Magnetic Force Between Two Balls (#1552) to practice the maximize variant, and Minimum Number of Days to Make m Bouquets (#1482) to see yet another feasibility function on the same skeleton.

Use YeetCode flashcards to drill pattern recognition. When you see a new problem, the first question should be: "Is the answer space monotonic?" If yes, you already know the solution structure. The flashcard approach locks in the trigger phrases and template so you can identify binary search on answer space problems in seconds during a real interview.