Stage 4: Advanced Techniques·Binary Search on Answer

Medium#10117 min readBinary SearchGreedyLeetCode

Capacity To Ship Packages

Binary search on capacity

Same template as #410. The greedy check is the same pattern.

Published Apr 16, 2026

Problem

A conveyor belt has weights[i] packages, in the order they must ship. You have days days and can pick any ship capacity. Each day the ship loads packages in their given order until the next one would exceed the capacity, then sails. You may not rearrange packages.

Return the minimum ship capacity that delivers everything within days days.

Input

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

Output

Explanation

Day 1: 1+2+3+4+5=15. Day 2: 6+7. Day 3: 8. Day 4: 9. Day 5: 10. No smaller capacity fits into 5 days.

Input

weights = [3, 2, 2, 4, 1, 4], days = 3

Output

Explanation

Day 1: 3+2. Day 2: 2+4. Day 3: 1+4.

Input

weights = [1, 2, 3, 1, 1], days = 4

Output

Intuition

The naive search is over ship capacities. Try each capacity from max(weights) upward and stop as soon as the greedy loading fits inside days. That works for small inputs but is wasteful — each probe takes O(n) and the capacity range can be huge.

The answer space is monotone: if capacity C works, then C + 1 also works (more headroom is never worse). If capacity C fails, C − 1 also fails. Swap the linear scan for binary search and the probe count drops from O(S) to O(log S).

Lower bound: max(weights) — nothing smaller could even lift the heaviest package. Upper bound: sum(weights) — one giant day. The predicate is a single greedy pass counting the number of days used.

This is the same skeleton as #410 (Split Array Largest Sum). Only the vocabulary changes: "piece max sum" becomes "ship capacity", "number of pieces" becomes "number of days".

Approach

Linear Scan Over Capacities

TimeO(n · S)

SpaceO(1)

Walk capacity C from max(weights) upward. For each C, run the greedy day-counter. The first C that produces days or fewer days is the answer.

Correct, obvious, and painfully slow when S = sum(weights) is large. Useful as a mental baseline and to prove the greedy predicate is right before swapping in binary search.

impl Solution {
    pub fn ship_within_days(weights: Vec<i32>, days: i32) -> i32 {
        let days = days as usize;
        let mut lo: i32 = 0;
        let mut hi: i32 = 0;
        for &w in &weights {
            if w > lo {
                lo = w;
            }
            hi += w;
        }

        let days_needed = |cap: i32| -> usize {
            let mut d: usize = 1;
            let mut cur: i32 = 0;
            for &w in &weights {
                if cur + w > cap {
                    d += 1;
                    cur = w;
                } else {
                    cur += w;
                }
            }
            d
        };

        for cap in lo..=hi {
            if days_needed(cap) <= days {
                return cap;
            }
        }
        hi
    }
}

Rust · runnable

function shipWithinDays(weights: number[], days: number): number {
  let lo = 0;
  let hi = 0;
  for (const w of weights) {
    if (w > lo) lo = w;
    hi += w;
  }

  const daysNeeded = (cap: number): number => {
    let d = 1;
    let cur = 0;
    for (const w of weights) {
      if (cur + w > cap) {
        d++;
        cur = w;
      } else {
        cur += w;
      }
    }
    return d;
  };

  for (let cap = lo; cap <= hi; cap++) {
    if (daysNeeded(cap) <= days) return cap;
  }
  return hi;
}

TypeScript · runnable

Binary Search on Capacity

TimeO(n log S)

SpaceO(1)

Recommended

Same predicate, logarithmic probe count. Lower-bound binary search over [max(weights), sum(weights)].

impl Solution {
    pub fn ship_within_days(weights: Vec<i32>, days: i32) -> i32 {
        let days = days as usize;
        let mut lo: i32 = 0;
        let mut hi: i32 = 0;
        for &w in &weights {
            if w > lo {
                lo = w;
            }
            hi += w;
        }

        let feasible = |cap: i32| -> bool {
            let mut d: usize = 1;
            let mut cur: i32 = 0;
            for &w in &weights {
                if cur + w > cap {
                    d += 1;
                    cur = w;
                    if d > days {
                        return false;
                    }
                } else {
                    cur += w;
                }
            }
            true
        };

        while lo < hi {
            let mid= lo + (hi - lo) / 2;
            if feasible(mid) {
                hi= mid;
            } else {
                lo= mid + 1;
            }
        }

        lo
    }
}

Rust · runnable

function shipWithinDays(weights: number[], days: number): number {
  let lo = 0;
  let hi = 0;
  for (const w of weights) {
    if (w > lo) lo = w;
    hi += w;
  }

  const feasible = (cap: number): boolean => {
    let d = 1;
    let cur = 0;
    for (const w of weights) {
      if (cur + w > cap) {
        d++;
        cur = w;
        if (d > days) return false;
      } else {
        cur += w;
      }
    }
    return true;
  };

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (feasible(mid)) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }

  return lo;
}

TypeScript · runnable

Trace

Binary search on weights = [1..10], days = 5. Start with [lo, hi] = [10, 55]:

lo	hi	mid	days(mid)	action
10	55	32	2	days ≤ 5, move hi to 32
10	32	21	3	days ≤ 5, move hi to 21
10	21	15	5	days ≤ 5, move hi to 15
10	15	12	6	days > 5, move lo to 13
13	15	14	6	days > 5, move lo to 15

Loop ends at lo = hi = 15. The greedy trace for cap 15: [1+2+3+4+5], [6+7], [8], [9], [10] — exactly 5 days. Any smaller cap forces a 6th day.

Edge cases

days = 1 — ship everything at once; answer is sum(weights). The upper bound is already feasible.
days ≥ n — each package on its own day works; answer is max(weights). The lower bound is feasible.
Single package — weights = [w]; answer is w regardless of days.
Very wide range — binary search is O(log(sum)), so even sum = 5 × 10⁸ costs under 30 probes.

💡

Tip

Notice the feasibility function short-circuits when the day count exceeds days. This avoids scanning the whole array on a clearly-infeasible capacity — a free constant-factor win that matters when n is large.

Takeaway

Once you recognize the "binary search on answer" skeleton, whole problem families collapse into a template. The greedy feasibility check is where the domain lives; the binary search is boilerplate.

This is the same algorithm you'd use to answer "what's the smallest truck that meets the SLA?" in a warehouse scheduler. The LeetCode framing is a clean rehearsal for that.

Hard#410

Split Array Largest Sum

Binary search on max sum. Check: can we split into ≤k parts each ≤ mid?

Medium#875

Koko Eating Bananas

Binary search on the ANSWER. This is the gateway to a whole class of hards.

Hard#2141

Maximum Running Time of N Computers

Binary search on time + greedy check on battery allocation.

Hard#774

Minimize Max Distance to Gas Station

Real-valued binary search. Use an epsilon or fixed iterations.

Problem

Intuition

Approach

Trace

Edge cases

Takeaway

More in Binary Search on Answer