Capacity to Ship Packages: Binary Search on the Answer

Packages must be shipped in the order given. weights[i] is the weight of the i-th package. Each day the ship is loaded with a run of packages from the front, without exceeding its capacity. Return the smallest capacity that clears every package within days days.

Examples

Input	Output	Why
`weights = [1,2,3,4,5,6,7,8,9,10], days = 5`	`15`	Days of 1–5, 6–7, 8, 9, 10.
`weights = [3,2,2,4,1,4], days = 3`	`6`	3+2, 2+4, 1+4.
`weights = [1,2,3,1,1], days = 4`	`3`	A capacity of 2 needs five days.

Constraints

1 ≤ days ≤ n ≤ 5 × 10⁴
1 ≤ weights[i] ≤ 500
Packages keep their order

Hints

Hint 1

Ask the easier question first: given a capacity C, can you finish in the allowed number of days? That is one greedy pass.

Hint 2

If capacity C works, does C + 1 also work? That monotonicity is what makes binary search legal.

Hint 3

The answer is between max(weights) — a single package must fit — and sum(weights), which is one day.

Dry run on `[3,2,2,4,1,4],3`

Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.

Step 1 / 6

Step 1 / 6

weights
302122431445
lo4hi16days3
The answer lies between max(weights) = 4 (one package must fit) and sum(weights) = 16 (everything in one day).
Step 2 / 6

capacities
4mid 1016
lo4hi16mid10daysNeeded2
Try capacity 10: the greedy split needs 2 days, which fits. So every capacity above 10 also works — discard the upper half.
Step 3 / 6

capacities
4mid 710
lo4hi10mid7daysNeeded3
Try capacity 7: the greedy split needs 3 days, which fits. So every capacity above 7 also works — discard the upper half.
Step 4 / 6

capacities
4mid 57
lo4hi7mid5daysNeeded4
Try capacity 5: the greedy split needs 4 days, which is too many. So no capacity at or below 5 works — discard the lower half.
Step 5 / 6

capacities
6mid 67
lo6hi7mid6daysNeeded3
Try capacity 6: the greedy split needs 3 days, which fits. So every capacity above 6 also works — discard the upper half.
Step 6 / 6

capacities
6mid 66
answer6
lo and hi meet at 6: the smallest capacity that clears the backlog in 3 days.

How to think about it

Two things turn this from a hard scheduling question into a short one.

Checking is easy. For a fixed capacity, greedily fill each day until the next package would overflow, then start a new day. That greedy split is optimal because delaying a package never lets you fit more later.
The check is monotone. If a capacity works, every larger capacity works. So the feasible capacities form a suffix of the number line, and binary search finds its first element.

Search the range [max(weights), sum(weights)]: below the maximum a single package would never fit, and the total always works. Each check is O(n) and the range halves each time, so the cost is O(n log(sum)). Recognising "the answer is a number, and verifying a candidate is cheaper than constructing it" is the transferable part — the same move solves minimum eating speed, splitting an array into k parts, and most "minimise the maximum" questions.

Complexity. Time O(n log Σw) · Space O(1)

The solution, in six languages

Each one is compiled and run against the test table before it is published. Java is reviewed by hand.

def ship_capacity(weights, days):
    def feasible(cap):
        used, load = 1, 0
        for w in weights:
            if load + w > cap:      # start a new day
                used += 1
                load = 0
            load += w
        return used <= days

    lo, hi = max(weights), sum(weights)
    while lo < hi:                  # find the first capacity that works
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

#include <vector>
#include <numeric>
#include <algorithm>

static bool feasible(const std::vector<int>& w, long long cap, int days) {
    int used = 1;
    long long load = 0;
    for (int x : w) {
        if (load + x > cap) { ++used; load = 0; }
        load += x;
    }
    return used <= days;
}

long long solve(const std::vector<int>& weights, int days) {
    long long lo = *std::max_element(weights.begin(), weights.end());
    long long hi = std::accumulate(weights.begin(), weights.end(), 0LL);
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;      // no overflow
        if (feasible(weights, mid, days)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

class Solution {
    private boolean feasible(int[] w, long cap, int days) {
        int used = 1;
        long load = 0;
        for (int x : w) {
            if (load + x > cap) { used++; load = 0; }
            load += x;
        }
        return used <= days;
    }

    public long shipCapacity(int[] weights, int days) {
        long lo = 0, hi = 0;
        for (int x : weights) { lo = Math.max(lo, x); hi += x; }
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (feasible(weights, mid, days)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
}

function shipCapacity(weights, days) {
  const feasible = (cap) => {
    let used = 1, load = 0;
    for (const w of weights) {
      if (load + w > cap) { used++; load = 0; }   // start a new day
      load += w;
    }
    return used <= days;
  };

  let lo = Math.max(...weights);
  let hi = weights.reduce((a, b) => a + b, 0);
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (feasible(mid)) hi = mid; else lo = mid + 1;
  }
  return lo;
}

fn feasible(weights: &[i64], cap: i64, days: i64) -> bool {
    let (mut used, mut load) = (1i64, 0i64);
    for &w in weights {
        if load + w > cap {
            used += 1;
            load = 0;
        }
        load += w;
    }
    used <= days
}

fn solve(weights: &[i64], days: i64) -> i64 {
    let mut lo = *weights.iter().max().unwrap();
    let mut hi: i64 = weights.iter().sum();
    while lo < hi {
        let mid = lo + (hi - lo) / 2;
        if feasible(weights, mid, days) { hi = mid } else { lo = mid + 1 }
    }
    lo
}

-- Greedy day count for a fixed capacity, then binary search the smallest feasible one.
daysNeeded :: [Int] -> Int -> Int
daysNeeded ws cap = go ws 0 1
  where
    go []     _    used = used
    go (w:rest) load used
      | load + w > cap = go rest w (used + 1)
      | otherwise      = go rest (load + w) used

solve :: [Int] -> Int -> Int
solve ws days = search (maximum ws) (sum ws)
  where
    search lo hi
      | lo >= hi  = lo
      | daysNeeded ws mid <= days = search lo mid
      | otherwise                 = search (mid + 1) hi
      where mid = lo + (hi - lo) `div` 2

Where people lose marks

Starting the search at 1 rather than max(weights): the feasibility check must still be written so it never loops forever on a package that cannot fit.
Returning the midpoint when the loop ends rather than the recorded low bound.
Using (lo + hi) / 2 with large bounds in C++ or Java. Prefer lo + (hi − lo) / 2.

Variants to try

Return the actual split, not just the capacity: replay the greedy pass once with the answer.
Packages can be reordered: the problem becomes bin packing, which is NP-hard.
Minimise days for a fixed capacity: that is the greedy pass on its own, with no search.

Next problems

Medium15 min

Minimum of a rotated sorted array

The input is not sorted, so the usual comparison is useless. Compare against the right end instead.

Open the problem →

Smallest ship that clears the backlog in D days

Examples

Constraints

Hints

Dry run on `[3,2,2,4,1,4],3`

How to think about it

The solution, in six languages

Where people lose marks

Variants to try

Next problems

Minimum of a rotated sorted array

Keep going

Minimum of a rotated sorted array

The pattern behind it

Smallest ship that clears the backlog in D days

Examples

Constraints

Hints

Dry run on [3,2,2,4,1,4],3

How to think about it

The solution, in six languages

Where people lose marks

Variants to try

Next problems

Minimum of a rotated sorted array

Keep going

Minimum of a rotated sorted array

The pattern behind it

Dry run on `[3,2,2,4,1,4],3`