Binary Search on Answer Space — Koko Eating Bananas, Capacity to Ship Packages

Most developers know binary search as "find a target in a sorted array." That's fine, but it's only half the story. There's a second form — arguably more powerful in interviews — where you're not searching an array at all. You're searching the range of possible answers.

The problem looks like this: you need to find the minimum speed, or the minimum capacity, or the smallest number of days that satisfies some constraint. The naive approach is to try every candidate answer from 1 upward. The fast approach is to binary search the answer range, testing each candidate in O(n). That's the pattern.

What Makes an Answer "Searchable"

Binary search only works on monotonic sequences. A sorted array is monotonic by value. The answer space is monotonic by the feasibility of the problem:

• If Koko can eat all bananas at speed 5, she can definitely eat them at speed 6 or 10.
• If a ship can deliver all packages in 7 days with capacity 500, it can definitely do it with capacity 600.

There's a threshold. Below it, the answer is infeasible. Above it, it's feasible. That boundary is what you binary search for.

Think of the feasibility check as a sorted boolean array: [false, false, false, true, true, true, true]. Binary search finds the first true — the minimum feasible answer.

How to recognize this pattern:

• "Find the minimum X such that you can accomplish Y"
• "Find the minimum capacity / speed / days / workers"
• There's a clear lower bound and upper bound on the answer
• You can verify if a given answer X is feasible in O(n) with a greedy pass

The Template

Before diving into specific problems, here's the universal structure:

// Generic binary search on answer space template
const solveMinimum = (input, constraint) => {
  // Define the range of possible answers
  let left = minPossibleAnswer(input);   // lower bound
  let right = maxPossibleAnswer(input);  // upper bound
 
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
 
    if (isFeasible(input, mid, constraint)) {
      right = mid;       // mid works, try to minimize further
    } else {
      left = mid + 1;    // mid fails, need a larger answer
    }
  }
 
  return left; // left === right === minimum feasible answer
};

Key things about this template:

• Loop condition is left < right (not <=) because we're converging to a value, not searching for one
• right = mid (not mid - 1) because mid itself might be the answer
• left = mid + 1 when infeasible — mid definitely isn't the answer
• When loop exits, left === right is your answer

Problem 1: Koko Eating Bananas (LeetCode 875)

Koko loves bananas. There are n piles of bananas, piles[i] bananas in each pile. She has h hours before guards return. Each hour she can eat k bananas from one pile (if the pile has fewer than k, she eats it all and doesn't eat another pile that hour).

Find the minimum integer k such that she can eat all bananas within h hours.

Input: piles = [3, 6, 7, 11], h = 8 Output: 4

Input: piles = [30, 11, 23, 4, 20], h = 5 Output: 30

Brute Force: Try Every Speed

// Input: piles = [3, 6, 7, 11], h = 8
// Output: 4
 
const minEatingSpeedBrute = (piles, h) => {
  const maxPile = Math.max(...piles);
 
  // Try every possible speed from 1 to maxPile
  for (let speed = 1; speed <= maxPile; speed++) {
    const hoursNeeded = piles.reduce((total, pile) => {
      return total + Math.ceil(pile / speed);
    }, 0);
 
    if (hoursNeeded <= h) return speed; // first speed that works is minimum
  }
 
  return maxPile;
};
// Time: O(n * maxPile) | Space: O(1)
// For piles up to 10^9, this is effectively O(n * 10^9) — too slow

This works but is far too slow for the given constraints (pile sizes up to 10^9). The interviewer will ask: "Is there a more efficient approach?"

Optimized: Binary Search on Speed

// Input: piles = [3, 6, 7, 11], h = 8
// Output: 4
 
const minEatingSpeed = (piles, h) => {
  // Answer space: [1, max(piles)]
  // Can never need to eat faster than the largest pile in one hour
  let left = 1;
  let right = Math.max(...piles);
 
  while (left < right) {
    const speed = left + Math.floor((right - left) / 2);
 
    // Feasibility check: can Koko finish all piles at this speed within h hours?
    const hoursNeeded = piles.reduce((total, pile) => {
      return total + Math.ceil(pile / speed);
    }, 0);
 
    if (hoursNeeded <= h) {
      right = speed;      // speed works, try slower
    } else {
      left = speed + 1;   // too slow, must go faster
    }
  }
 
  return left;
};
// Time: O(n log M) where M = max(piles) | Space: O(1)

Let's trace the example: piles = [3, 6, 7, 11], h = 8

• Answer range: [1, 11]
• mid=6: hours = ceil(3/6)+ceil(6/6)+ceil(7/6)+ceil(11/6) = 1+1+2+2 = 6. 6 ≤ 8, feasible → right=6
• mid=3: hours = 1+2+3+4 = 10. 10 > 8, infeasible → left=4
• mid=5: hours = 1+2+2+3 = 8. 8 ≤ 8, feasible → right=5
• mid=4: hours = ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8. 8 ≤ 8, feasible → right=4
• left=4, right=4. Done. Answer: 4. ✓

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

A conveyor belt has packages in order, with weights weights[i]. You must ship them all in days days. Packages cannot be reordered. Each day, you load packages onto the ship until the next package would exceed capacity, then stop and ship. Find the minimum ship capacity.

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

Input: weights = [3, 2, 2, 4, 1, 4], days = 3 Output: 6

The Feasibility Check

For a given capacity, simulating the shipping process is straightforward: greedily load packages until adding the next would exceed capacity, then start a new day.

// Feasibility check: can all packages be shipped in 'days' days with this capacity?
const canShip = (weights, capacity, days) => {
  let currentLoad = 0;
  let daysNeeded = 1;
 
  for (const weight of weights) {
    // A single package heavier than the ship can never be shipped, no matter
    // how many days you have. Without this line the greedy silently overloads
    // the ship and reports success — see the callout below.
    if (weight > capacity) return false;
 
    if (currentLoad + weight > capacity) {
      // This package starts a new day
      daysNeeded++;
      currentLoad = 0;
    }
    currentLoad += weight;
  }
 
  return daysNeeded <= days;
};

That first if is not decoration. Drop it and the greedy resets currentLoad to 0 and then immediately does currentLoad += weight, leaving a load of weight on a ship whose capacity is smaller than weight. Nothing ever notices:

// without the `weight > capacity` guard:
canShip([5], 3, 1000)    // true  ← a 5kg package on a 3kg ship
canShip([10, 10], 1, 5)  // true
canShip([1, 2, 3], 0, 9) // true  ← capacity zero
 
// with the guard:
canShip([5], 3, 1000)    // false
canShip([10, 10], 1, 5)  // false
canShip([1, 2, 3], 0, 9) // false
canShip([5], 5, 1)       // true   (fits exactly — still feasible)

Brute Force: Try Every Capacity

// Input: weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5
// Output: 15
 
const shipWithinDaysBrute = (weights, days) => {
  const minCapacity = Math.max(...weights); // must fit the heaviest package
  const maxCapacity = weights.reduce((sum, w) => sum + w, 0); // ship all in 1 day
 
  for (let capacity = minCapacity; capacity <= maxCapacity; capacity++) {
    if (canShip(weights, capacity, days)) return capacity;
  }
  return maxCapacity;
};
// Time: O(n * sum(weights)) | Space: O(1)
// Way too slow for weights up to 500 with n up to 50000

Optimized: Binary Search on Capacity

// Input: weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5
// Output: 15
 
const shipWithinDays = (weights, days) => {
  // Lower bound: must be at least the heaviest package (can't break it up)
  // Upper bound: ship everything in one day
  let left = 0;
  let right = 0;
 
  for (const weight of weights) {
    left = Math.max(left, weight);  // heaviest package
    right += weight;                 // total weight
  }
 
  while (left < right) {
    const capacity = left + Math.floor((right - left) / 2);
 
    if (canShip(weights, capacity, days)) {
      right = capacity;      // capacity sufficient, try smaller
    } else {
      left = capacity + 1;   // insufficient, need more
    }
  }
 
  return left;
};
// Time: O(n log S) where S = sum(weights) | Space: O(1)

Trace for weights = [3, 2, 2, 4, 1, 4], days = 3:

• left=4 (max weight), right=16 (sum)
• capacity=10: [3,2,2]=7 day1, [4,1,4]=9 day2 = 2 days. Feasible → right=10
• capacity=7: [3,2,2]=7✓ day1, [4,1]=5 day2, [4] day3 = 3 days. Feasible → right=7
• capacity=5: [3,2]=5 day1, [2]=2... wait: 2+4=6>5, so [2] day2, [4,1]=5 day3, [4] day4 = 4>3. Infeasible → left=6
• capacity=6: [3,2]=5 day1, [2,4]=6 day2, [1,4]=5 day3 = 3 days. Feasible → right=6
• left=6, right=6. Done. Answer: 6. ✓

Problem 3: Split Array Largest Sum (LeetCode 410)

Split nums into exactly k non-empty subarrays to minimize the largest subarray sum.

Input: nums = [7, 2, 5, 10, 8], k = 2 Output: 18

This is structurally identical to Capacity to Ship. The answer is "the minimum capacity" where capacity = maximum subarray sum. The feasibility check is the same greedy: greedily add numbers to the current subarray; when the next would exceed capacity, start a new subarray. If you can fit everything into k subarrays, the capacity is viable.

// Input: nums = [7, 2, 5, 10, 8], k = 2
// Output: 18
 
const splitArray = (nums, k) => {
  let left = Math.max(...nums);  // at minimum, largest single element
  let right = nums.reduce((sum, n) => sum + n, 0); // entire array as one subarray
 
  const canSplit = (maxSum) => {
    let currentSum = 0;
    let subarrays = 1;
 
    for (const num of nums) {
      if (num > maxSum) return false; // fail closed, same as canShip
      if (currentSum + num > maxSum) {
        subarrays++;
        currentSum = 0;
      }
      currentSum += num;
    }
 
    return subarrays <= k; // true if we fit within k splits
  };
 
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
 
    if (canSplit(mid)) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
 
  return left;
};
// Time: O(n log S) where S = sum(nums) | Space: O(1)

Notice: this is nearly word-for-word the Ship Packages solution. The pattern is the same. Only the problem framing changed.

Complexity Cheat Sheet

M = max element, S = sum of elements.

Interview Tips

Tip 1: The moment you hear "find the minimum X such that Y is possible," say "I think this is binary search on the answer space" out loud. Naming the pattern signals recognition. Then walk the interviewer through: "The answer space is [lower, upper], the feasibility check is a greedy O(n) pass, and the property is monotonic — so binary search applies."

Tip 2: Get your bounds right before writing the loop. For Koko: left = 1, right = max(piles). For Ship Packages: left = max(weights), right = sum(weights). Getting these wrong means your binary search might return an out-of-bounds answer. Spend 30 seconds explicitly reasoning about "what's the minimum possible answer?" and "what's the maximum possible answer?"

Tip 3: The feasibility check should be a clean, separate function — and it has to be correct standalone, not just correct inside your loop. In interviews, write canShip or isFeasible before the binary search loop. It shows you can decompose problems, and you can test it independently. But note the trap that decomposition exposes: the naive greedy is only correct for the capacities the search actually asks about, because left starts at max(weights). Call it yourself with anything smaller — canShip([5], 3, 1000) — and the unguarded version returns true. If you're going to present it as a standalone, reusable predicate, it needs the weight > capacity early return so that its contract holds for every input, not just the ones its caller happens to pass. Adding that guard changes nothing about the answers shipWithinDays produces (I checked 40,000 random inputs against a brute-force scan over every capacity — identical results); it only makes the predicate honest when used on its own.