Binary Search on Answer Space

Suppose you have an array of positive integers and you need to split it into k contiguous subarrays so that the largest subarray sum is as small as possible. This is LeetCode 410, Split Array Largest Sum, and it is one of those problems that looks like it should be solved with dynamic programming. You could define dp[i][j] as the minimum largest-sum when splitting the first i elements into j groups, and you would be right: that works. But it runs in $O(n^2 \cdot k)$ time and the code is fiddly. There is a far more elegant approach hiding in plain sight, and once you see it, you will start recognizing it everywhere.

The trick is to stop searching for the best split and instead binary search on the answer itself.

The insight: search on the answer

Here is the mental shift. Instead of asking "what is the optimal way to split this array?", ask a different question: "if I told you that no subarray is allowed to exceed a capacity of X, could you split the array into k or fewer parts?"

That question is dramatically easier to answer. You just walk left to right, greedily packing elements into the current group. When adding the next element would push the group sum past X, you start a new group. If you finish with k or fewer groups, then X is feasible. If you need more than k groups, X is too small.

The beautiful part is that feasibility is monotonic. If a capacity of X works, then X + 1 also works, since a larger budget can only make things easier. And if X is too small, then X - 1 is also too small. This monotonicity is exactly what binary search requires. There is a sharp boundary between "too small" and "feasible," and binary search finds it in $O(\log(\text{range}))$ probes.

The feasibility check

The feasibility function is the heart of this pattern. For Split Array Largest Sum, it looks like this: walk through the array, maintaining a running sum for the current group. When adding the next element would exceed the capacity, close the current group and start a new one. Count how many groups you need. If the count is within budget, return True.

def feasible(nums, cap, k):
    groups = 1
    current_sum = 0
    for x in nums:
        if current_sum + x > cap:
            groups += 1
            current_sum = 0
        current_sum += x
    return groups <= k

This runs in $O(n)$: a single pass through the array. No recursion, no memoization, no complicated state.

Walking through an example

Take nums = [7, 2, 5, 10, 8] with k = 2. We need to split this into at most 2 contiguous subarrays, minimizing the maximum subarray sum.

First, what are the bounds for our binary search? The smallest possible answer is max(nums) = 10, because every element must fit in some group. The largest possible answer is sum(nums) = 32, which corresponds to putting everything in one group. So lo = 10 and hi = 32.

Iteration 1: mid = (10 + 32) // 2 = 21. Is capacity 21 feasible? Walk through: 7 (sum=7), then 7+2=9, then 9+5=14, then 14+10=24 > 21, so start a new group. Groups so far: 1 completed, now in group 2. Continue: 10 (sum=10), then 10+8=18. Done with 2 groups. 2 <= 2, so feasible. Set hi = 21.

Iteration 2: mid = (10 + 21) // 2 = 15. Is 15 feasible? Walk through: 7, 7+2=9, 9+5=14, 14+10=24 > 15, new group. 10, 10+8=18 > 15, new group. 8. That is 3 groups, but we only have budget for 2. Not feasible. Set lo = 16.

Iteration 3: mid = (16 + 21) // 2 = 18. Is 18 feasible? Walk through: 7, 9, 14, 24 > 18, new group. 10, 18. Two groups total. Feasible. Set hi = 18.

Iteration 4: mid = (16 + 18) // 2 = 17. Is 17 feasible? Walk through: 7, 9, 14, 24 > 17, new group. 10, 18 > 17, new group. 8. Three groups. Not feasible. Set lo = 18.

Now lo == hi == 18. The answer is 18, corresponding to the split [7, 2, 5] | [10, 8] with subarray sums 14 and 18.

The complete solution

def splitArray(nums, k):
    def feasible(cap):
        groups = 1
        current_sum = 0
        for x in nums:
            if current_sum + x > cap:
                groups += 1
                current_sum = 0
            current_sum += x
        return groups <= k

    lo, hi = max(nums), sum(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Koko Eating Bananas

The problem LeetCode 875 dresses the same idea in a different story. Koko has piles of bananas and h hours to eat them all. Each hour, she picks a pile and eats up to speed bananas from it. If the pile has fewer than speed bananas, she finishes that pile and waits out the rest of the hour. What is the minimum speed that lets her finish in time?

The answer space is clear: the minimum speed is 1 (eat one banana per hour), and the maximum useful speed is max(piles) (she can finish any pile in one hour). Monotonicity holds: if speed s is fast enough, then s + 1 is also fast enough.

The feasibility check changes: for a given speed, calculate how many hours each pile takes (ceiling division: (pile + speed - 1) // speed), sum those hours, and check whether the total is within h.

def minEatingSpeed(piles, h):
    def feasible(speed):
        hours = 0
        for pile in piles:
            hours += (pile + speed - 1) // speed
        return hours <= h

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

The structure is identical. Only the feasibility check is different.

Capacity to Ship Packages Within D Days

Consider LeetCode 1011, yet another instance. You have packages with given weights that must be shipped in order over d days. What is the minimum ship capacity? The answer range is [max(weights), sum(weights)]. The feasibility check is essentially the same as Split Array Largest Sum: greedily load packages onto the current day's ship until the next package would exceed capacity, then start a new day.

def shipWithinDays(weights, days):
    def feasible(cap):
        day_count = 1
        current_load = 0
        for w in weights:
            if current_load + w > cap:
                day_count += 1
                current_load = 0
            current_load += w
        return day_count <= days

    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

If this looks almost identical to Split Array Largest Sum, that is because it is. The outer binary search is exactly the same. The inner check is exactly the same. They are the same problem wearing different hats.

The general pattern

Every binary-search-on-answer problem has the same skeleton:

1. Identify the answer range. Find the smallest possible answer (lo) and the largest possible answer (hi). For "minimize the maximum" problems, lo is usually the maximum single element and hi is the total sum.

1. Write a feasible(mid) function. This is where the real work is. It takes a candidate answer and returns True if that answer is achievable. The feasibility check is typically a greedy $O(n)$ scan.

1. Binary search. Use the lo < hi template with hi = mid when feasible and lo = mid + 1 when not. Return lo.

Why lo < hi with hi = mid

This is a subtle but important detail. When feasible(mid) returns True, you know mid is a valid answer, but there might be a smaller valid answer. So you set hi = mid, keeping mid in the search space. When it returns False, mid is definitely not the answer, so you can safely exclude it with lo = mid + 1.

The loop terminates when lo == hi, at which point they both point to the smallest feasible value. If you instead used hi = mid - 1, you might skip over the answer: mid could be the exact boundary, and shrinking past it loses it forever.

This is one of the most common sources of binary search bugs. When in doubt, use lo < hi with hi = mid for "find the minimum feasible" problems, and lo < hi with lo = mid + 1 and hi = mid (never mid - 1) as your default.

Common mistakes

Wrong bounds. If you set lo too high, you might miss the answer. If you set hi too low, same problem. For Split Array Largest Sum, setting lo = 0 would still produce the correct answer (just slower), but setting lo = min(nums) instead of max(nums) means your feasibility check might encounter an element larger than the capacity, which the greedy algorithm does not handle well.

Feasibility logic errors. The greedy check must match the problem constraints exactly. In Split Array Largest Sum, you start with groups = 1 (not 0) because you are already in the first group. Off-by-one errors here silently shift your answer by one.

Forgetting to handle single elements. If any single element exceeds the capacity, the problem is infeasible. Setting lo = max(nums) ensures this never happens: you never test a capacity smaller than the largest element.

Minimize Max Distance to Gas Station

With LeetCode 774 comes a continuous twist. You have gas stations at given positions along a highway, and you can add k new stations anywhere. You want to minimize the maximum distance between adjacent stations.

The answer space is continuous: lo = 0 and hi = max gap between consecutive stations. For a candidate maximum gap d, the feasibility check counts how many new stations you need. For each existing gap g, you need ceil(g / d) - 1 stations to break it into pieces no larger than d. If the total is within k, d is feasible.

Because the answer is a real number, use a fixed number of iterations (around 100) or loop while hi - lo > 1e-6.

def minmaxGasDist(stations, k):
    def feasible(d):
        count = 0
        for i in range(len(stations) - 1):
            gap = stations[i + 1] - stations[i]
            count += int(gap / d)
        return count <= k

    lo, hi = 0, max(stations[i + 1] - stations[i]
                     for i in range(len(stations) - 1))
    for _ in range(100):
        mid = (lo + hi) / 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid
    return lo

Note two differences from the integer variants. First, lo = mid instead of lo = mid + 1, because mid is a real number and we cannot "step past" it. Second, we loop a fixed number of times rather than checking lo < hi, since floating-point equality is unreliable. After 100 iterations the search range shrinks by a factor of $2^{100}$, which is far more precision than you need.

Minimum Number of Days to Make m Bouquets

Take LeetCode 1482, which searches on time. You have n flowers, each blooming on a given day. You need m bouquets, each requiring k adjacent bloomed flowers. What is the earliest day you can make all bouquets?

The answer range is [min(bloomDay), max(bloomDay)]. For a candidate day d, walk through the array counting consecutive flowers that have bloomed (i.e., bloomDay[i] <= d). Every time the streak reaches k, you have one bouquet and reset the streak. If you collect m bouquets, d is feasible.

def minDays(bloomDay, m, k):
    if m * k > len(bloomDay):
        return -1

    def feasible(day):
        bouquets = 0
        streak = 0
        for b in bloomDay:
            if b <= day:
                streak += 1
                if streak == k:
                    bouquets += 1
                    streak = 0
            else:
                streak = 0
        return bouquets >= m

    lo, hi = min(bloomDay), max(bloomDay)
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

The early guard m * k > len(bloomDay) handles the impossible case: if you need more flowers than exist, no amount of waiting helps.

Complexity analysis

The binary search runs $O(\log(hi - lo))$ iterations. For Split Array Largest Sum, the range is sum(nums) - max(nums), which is at most $O(n \cdot \text{max\_val})$. Each iteration runs the feasibility check in $O(n)$. So the total time complexity is $O(n \cdot \log(\text{sum} - \text{max}))$, which in practice is $O(n \cdot \log(n \cdot \text{max\_val}))$.

Space complexity is $O(1)$: you only need a few variables for the binary search and the greedy scan.

Compared to the $O(n^2 \cdot k)$ DP approach, this is dramatically faster and far simpler to implement. That is the magic of binary search on the answer space: you replace a hard optimization problem with a sequence of easy yes/no questions.

Recognizing this pattern

You're probably looking at binary search on the answer when:

• The problem asks to "minimize the maximum" or "maximize the minimum" of something.
• You can phrase the question as "Can we achieve X with budget Y?", a feasibility predicate that is monotonic in X.
• Brute-forcing the optimum is hard, but checking feasibility for a fixed candidate value is an easy greedy or simulation.
• The answer is a number bounded by an obvious range (e.g., max element to total sum, 1 to max-coord) and you want $O(\log(\text{range}) \cdot n)$.

Common templates:

• Minimize the maximum: binary search on the cap; predicate counts greedy groups. Example: Split Array Largest Sum.
• Maximize the minimum: binary search on the floor; predicate greedily places items so the minimum gap is at least mid. Example: Magnetic Force Between Two Balls.
• Minimum time / capacity / speed: binary search the rate; predicate simulates whether the deadline is met. Example: Koko Eating Bananas.
• Smallest divisor or budget: binary search the divisor; predicate sums ceilings. Example: Find the Smallest Divisor Given a Threshold.
• Kth smallest in a structured set: binary search the value; predicate counts how many elements are <= mid. Example: Kth Smallest Element in a Sorted Matrix.