Binary Search on Answer: Advanced Problems

Binary search on the answer is one of the most powerful interview patterns. Instead of searching for a target in a sorted array, you search over the space of possible answers and use a feasibility check to guide the search. This post dives into five advanced problems that all follow the same skeleton.

---

The Two Templates

Every binary-search-on-answer problem falls into one of two categories.

Template 1: Minimize the Maximum

You want the smallest value x such that some condition is feasible.

def minimize_the_maximum(lo, hi, is_feasible):
    """
    Find the smallest x in [lo, hi] where is_feasible(x) is True.

    Precondition: is_feasible is monotonic — once True, stays True.

    Time: O(log(hi - lo) * cost_of_feasibility_check)
    """
    while lo < hi:
        mid = (lo + hi) // 2
        if is_feasible(mid):
            hi = mid        # mid works, try smaller
        else:
            lo = mid + 1    # mid doesn't work, go larger
    return lo

Template 2: Maximize the Minimum

You want the largest value x such that some condition is feasible.

def maximize_the_minimum(lo, hi, is_feasible):
    """
    Find the largest x in [lo, hi] where is_feasible(x) is True.

    Precondition: is_feasible is monotonic — once False, stays False.

    Time: O(log(hi - lo) * cost_of_feasibility_check)
    """
    while lo < hi:
        mid = (lo + hi + 1) // 2   # Round up to avoid infinite loop
        if is_feasible(mid):
            lo = mid        # mid works, try larger
        else:
            hi = mid - 1    # mid doesn't work, go smaller
    return lo

Critical difference: In Template 2, use mid = (lo + hi + 1) // 2 (ceiling division) to avoid infinite loops when lo + 1 == hi.

---

Problem 1: Koko Eating Bananas (LeetCode 875)

Problem: Koko has n piles of bananas. She can eat at speed k bananas per hour — if a pile has fewer than k bananas, she finishes it in that hour and doesn’t eat more. She has h hours. Find the minimum k such that she can eat all bananas within h hours.

Analysis

• Answer space: [1, max(piles)]
• Category: Minimize the maximum (minimize eating speed)
• Feasibility: Can she finish in h hours at speed mid?

import math

def min_eating_speed(piles, h):
    """
    LeetCode 875: Koko Eating Bananas

    Binary search on the eating speed k.
    For each k, check if total hours <= h.

    Time: O(n * log(max(piles)))
    Space: O(1)
    """
    def hours_needed(speed):
        return sum(math.ceil(p / speed) for p in piles)

    lo, hi = 1, max(piles)

    while lo < hi:
        mid = (lo + hi) // 2
        if hours_needed(mid) <= h:
            hi = mid        # Can eat slower
        else:
            lo = mid + 1    # Too slow, eat faster

    return lo

Walkthrough

piles = [3, 6, 7, 11]
h = 8

# lo=1, hi=11
# mid=6: hours = ceil(3/6)+ceil(6/6)+ceil(7/6)+ceil(11/6) = 1+1+2+2 = 6 <= 8 → hi=6
# mid=3: hours = 1+2+3+4 = 10 > 8 → lo=4
# mid=5: hours = 1+2+2+3 = 8 <= 8 → hi=5
# mid=4: hours = 1+2+2+3 = 8 <= 8 → hi=4
# lo == hi == 4 → answer is 4

print(min_eating_speed([3, 6, 7, 11], 8))   # Output: 4
print(min_eating_speed([30, 11, 23, 4, 20], 5))  # Output: 30
print(min_eating_speed([30, 11, 23, 4, 20], 6))  # Output: 23

---

Problem 2: Capacity to Ship Packages Within D Days (LeetCode 1011)

Problem: Packages with weights weights[i] must be shipped in order within D days. Find the minimum ship capacity.

Analysis

• Answer space: [max(weights), sum(weights)]
• Category: Minimize the maximum (minimize capacity)
• Feasibility: Can we ship within D days at capacity mid?

def ship_within_days(weights, days):
    """
    LeetCode 1011: Capacity To Ship Packages Within D Days

    Binary search on the ship capacity.
    Greedy check: load packages until exceeding capacity, then start a new day.

    Time: O(n * log(sum(weights) - max(weights)))
    Space: O(1)
    """
    def can_ship(capacity):
        day_count = 1
        current_load = 0
        for w in weights:
            if current_load + w > capacity:
                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 can_ship(mid):
            hi = mid
        else:
            lo = mid + 1

    return lo

Walkthrough

weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
days = 5

# lo=10, hi=55
# mid=32: days_needed=2 <= 5 → hi=32
# mid=21: days_needed=2 <= 5 → hi=21
# mid=15: days_needed=4 <= 5 → hi=15
# mid=12: days_needed=5 <= 5 → hi=12  (load: [1,2,3,4|5,6|7|8|9,10]... no)
# Actually: [1,2,3,4,2=12? no, let's recount]
# mid=15: [1,2,3,4,5|6,7|8|9,10]... 
# Eventually converges to 15

print(ship_within_days([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5))  # Output: 15
print(ship_within_days([3, 2, 2, 4, 1, 4], 3))  # Output: 6

Why the lower bound is max(weights): Every package must fit on the ship. If capacity < max(weights), some package can never be shipped.

---

Problem 3: Split Array Largest Sum (LeetCode 410)

Problem: Split an array into k non-empty contiguous subarrays to minimize the largest subarray sum.

Analysis

This is the same structure as ship capacity — instead of “days,” think “number of subarrays.”

• Answer space: [max(nums), sum(nums)]
• Category: Minimize the maximum (minimize the largest partition sum)
• Feasibility: Can we split into <= k parts where each part sums to <= mid?

def split_array(nums, k):
    """
    LeetCode 410: Split Array Largest Sum

    Binary search on the maximum allowed subarray sum.
    Greedy: accumulate until exceeding the limit, then start new subarray.

    Time: O(n * log(sum(nums) - max(nums)))
    Space: O(1)
    """
    def can_split(max_sum):
        parts = 1
        current_sum = 0
        for num in nums:
            if current_sum + num > max_sum:
                parts += 1
                current_sum = 0
            current_sum += num
        return parts <= k

    lo, hi = max(nums), sum(nums)

    while lo < hi:
        mid = (lo + hi) // 2
        if can_split(mid):
            hi = mid
        else:
            lo = mid + 1

    return lo

Example

print(split_array([7, 2, 5, 10, 8], 2))  # Output: 18
# Split: [7, 2, 5] + [10, 8] → max(14, 18) = 18
# Can we do 17? [7,2,5|10,8] → 14,18 no. [7,2,5,10|8] → 24,8 no.

print(split_array([1, 2, 3, 4, 5], 2))   # Output: 9
# Split: [1,2,3,4] + [5] → 10,5 or [1,2,3] + [4,5] → 6,9 → answer 9

print(split_array([1, 4, 4], 3))          # Output: 4

The Common Pattern

Notice that Problems 2 and 3 have identical feasibility checks — the only difference is the problem framing (days vs partitions, capacity vs max sum). This is a hallmark of binary search on answer: different-sounding problems share the same skeleton.

---

Problem 4: Minimize Max Distance to Gas Station (LeetCode 774)

Problem: There are gas stations at positions stations[i] on a road. You can add k new stations. Minimize the maximum distance between adjacent stations.

Analysis

This problem introduces real-valued binary search — the answer is a floating-point number.

• Answer space: [0, max gap between consecutive stations]
• Category: Minimize the maximum distance
• Feasibility: With max distance d, how many stations are needed? If <= k, feasible.

def min_max_distance(stations, k):
    """
    LeetCode 774: Minimize Max Distance to Gas Station

    Binary search on the answer (a real number).
    For a given max distance d, count how many stations
    we need to insert in each gap.

    Time: O(n * log((max_gap) / epsilon))
    Space: O(1)
    """
    def stations_needed(max_dist):
        """Count new stations needed to ensure all gaps <= max_dist."""
        count = 0
        for i in range(len(stations) - 1):
            gap = stations[i + 1] - stations[i]
            # Number of new stations in this gap
            count += int(gap / max_dist)
            # If gap is exactly divisible, we need one fewer
            if gap / max_dist == int(gap / max_dist):
                count -= 1
        return count

    # Simpler feasibility using math.ceil
    def stations_needed_v2(max_dist):
        count = 0
        for i in range(len(stations) - 1):
            gap = stations[i + 1] - stations[i]
            # We split this gap into ceil(gap / max_dist) segments
            # needing ceil(gap/max_dist) - 1 new stations
            import math
            count += math.ceil(gap / max_dist) - 1
        return count

    lo, hi = 0.0, max(
        stations[i + 1] - stations[i]
        for i in range(len(stations) - 1)
    )

    # Binary search with precision
    for _ in range(100):  # ~10^-30 precision, more than enough
        mid = (lo + hi) / 2
        if stations_needed_v2(mid) <= k:
            hi = mid    # Can achieve smaller max distance
        else:
            lo = mid    # Need larger max distance

    return round(hi, 6)

Key Insight: Iteration Count Instead of Epsilon

For floating-point binary search, iterating a fixed number of times (e.g., 100) is safer than checking hi - lo {'<'} epsilon because:

• No risk of infinite loops from floating-point precision issues
• 100 iterations give roughly 10^-30 precision
• Simpler and more robust

Example

print(min_max_distance([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 9))
# Output: 0.5 — add one station in each gap

print(min_max_distance([1, 5, 10], 1))
# gap1=4, gap2=5, add 1 station
# Best: add in gap2 → [1, 5, 7.5, 10] → max gap = 4.0
# Output: 4.0 (can't reduce gap1 without using the station there)

---

Problem 5: Magnetic Force Between Two Balls (LeetCode 1552)

Problem: Place m balls in n baskets at given positions. Maximize the minimum magnetic force (distance) between any two balls.

Analysis

• Answer space: [1, (max_pos - min_pos) // (m - 1)]
• Category: Maximize the minimum distance
• Feasibility: Can we place all m balls with minimum gap >= mid?

def max_distance(position, m):
    """
    LeetCode 1552: Magnetic Force Between Two Balls

    Sort positions. Binary search on the minimum distance.
    Greedy: place balls left to right, each at the first
    position that's >= last_placed + min_dist.

    Time: O(n log n + n * log(max_pos - min_pos))
    Space: O(1) (ignoring sort)
    """
    position.sort()

    def can_place(min_dist):
        """Can we place m balls with at least min_dist between each pair?"""
        balls_placed = 1
        last_pos = position[0]

        for i in range(1, len(position)):
            if position[i] - last_pos >= min_dist:
                balls_placed += 1
                last_pos = position[i]
                if balls_placed == m:
                    return True

        return balls_placed >= m

    lo = 1
    hi = (position[-1] - position[0]) // (m - 1)

    while lo < hi:
        mid = (lo + hi + 1) // 2   # Round up for maximize template
        if can_place(mid):
            lo = mid        # This distance works, try larger
        else:
            hi = mid - 1    # Too far apart, reduce distance

    return lo

Example

print(max_distance([1, 2, 3, 4, 7], 3))  # Output: 3
# Place at 1, 4, 7 → min distance = 3

print(max_distance([5, 4, 3, 2, 1, 1000000000], 2))  # Output: 999999999
# Place at 1 and 1000000000

Why Round Up?

In the maximize template, if we use mid = (lo + hi) // 2 when lo = 3, hi = 4:

• mid = 3, if feasible, lo = 3 — infinite loop!

With mid = (lo + hi + 1) // 2:

• mid = 4, if feasible, lo = 4, loop ends.

---

Pattern Recognition Cheat Sheet

Problem Clue	Template	Answer Space
”Minimum speed/capacity such that…”	Minimize max	[1, max_val] to sum
”Split into k parts, minimize largest”	Minimize max	[max(arr), sum(arr)]
”Place items, maximize minimum gap”	Maximize min	[1, range // (k-1)]
”Minimize maximum distance/time”	Minimize max	[0, max_gap]
”Maximize minimum distance/value”	Maximize min	[1, total_range]

How to Identify Binary Search on Answer

1. Monotonic feasibility: If answer x works, then x + 1 also works (or vice versa).
2. Answer space is bounded: You know the minimum and maximum possible answer.
3. Feasibility check is fast: Usually O(n) greedy scan.
4. The problem asks for an optimal value, not a count or enumeration.

---

Complexity Summary

Problem	Time	Space
Koko Eating Bananas	O(n * log(max(piles)))	O(1)
Ship Packages	O(n * log(sum - max))	O(1)
Split Array Largest Sum	O(n * log(sum - max))	O(1)
Gas Station Distance	O(n * log(max_gap / eps))	O(1)
Magnetic Force	O(n log n + n * log(range))	O(1)

---

Practice Problems

Problem	Platform	Difficulty	Category
Koko Eating Bananas	LeetCode 875	Medium	Minimize max
Capacity To Ship Packages	LeetCode 1011	Medium	Minimize max
Split Array Largest Sum	LeetCode 410	Hard	Minimize max
Minimize Max Distance to Gas Station	LeetCode 774	Hard	Minimize max (float)
Magnetic Force Between Two Balls	LeetCode 1552	Medium	Maximize min
Aggressive Cows	SPOJ	Medium	Maximize min
Painter’s Partition	InterviewBit	Hard	Minimize max
Allocate Minimum Pages	GFG	Medium	Minimize max
Cutting Ribbons	LeetCode 1891	Medium	Maximize min
Minimum Speed to Arrive on Time	LeetCode 1870	Medium	Minimize max

---

Key Takeaways

1. Two templates cover nearly every problem: minimize-the-maximum (round down, move hi) and maximize-the-minimum (round up, move lo).
2. The feasibility check is always greedy — iterate once through the input and check if the candidate answer works.
3. Bounds matter: lower bound is the minimum possible answer (often max(arr) or 1), upper bound is the maximum (often sum(arr) or the full range).
4. For floating-point answers, use a fixed iteration count (100) instead of an epsilon check.
5. When in doubt, check monotonicity: if answer x is feasible and x + 1 is also feasible, binary search works.