Code Logo

Capacity To Ship Packages

Published at24 Jul 2026
Created by
Medium 0 views
Like0

A ship must transport packages across the ocean within a given number of days. Packages are loaded in order, and the ship cannot reorder them. Each day the ship loads as many packages as possible without exceeding its capacity. Find the minimum integer capacity that allows all packages to be shipped within the specified days.

This is a classic binary search on the answer problem. The lower bound of the capacity is the heaviest single package (since a ship must carry at least one package). The upper bound is the sum of all package weights (if everything ships in one day). Binary search between these bounds to find the smallest capacity that works.

The feasibility check simulates loading: iterate through packages, accumulate weight, and when adding the next package would exceed capacity, increment the day count and reset. If the total days needed is at most the given days, the capacity is feasible. This check is O(n), and combined with binary search gives O(n log sum) time.

Edge cases include days equal to the number of packages (capacity = max weight), days = 1 (capacity = total weight), and packages with zero weight (handle as regular items).

The binary search on answer pattern applies whenever the search space is monotonic: if capacity C works, any capacity larger than C also works. This property ensures correctness when narrowing the search range.

Example Input & Output

Example 1
Input
[5,5,5,5], 1
Output
20
Explanation

All in one day, capacity = sum 20.

Example 2
Input
[1,2,3,4,5,6,7,8,9,10], 5
Output
15
Explanation

Capacity 15 ships in 5 days.

Example 3
Input
[1,2,3,1,1], 4
Output
3
Explanation

Capacity 3 (max weight) ships in 4 days (one per day).

Example 4
Input
[10,10,10,10], 4
Output
10
Explanation

Each package its own day, capacity = max 10.

Example 5
Input
[3,2,2,4,1,4], 3
Output
6
Explanation

Capacity 6 ships in 3 days.

Algorithm Flow

Recommendation Algorithm Flow for Capacity To Ship Packages
Recommendation Algorithm Flow for Capacity To Ship Packages

Solution Approach

Binary search between max(weights) and sum(weights). Feasibility: simulate daily loading and count days needed.

function solution(weights, days) {
  var lo = 0, hi = 0;
  for (var i = 0; i < weights.length; i++) {
    if (weights[i] > lo) lo = weights[i];
    hi += weights[i];
  }
  function canShip(cap) {
    var total = 0, d = 1;
    for (var i = 0; i < weights.length; i++) {
      if (total + weights[i] > cap) { d++; total = 0; }
      total += weights[i];
    }
    return d <= days;
  }
  while (lo < hi) {
    var mid = Math.floor((lo + hi) / 2);
    if (canShip(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

Time O(n log S), Space O(1).

Best Answers

java
class Solution {
    public int solution(int[] weights, int days) {
        int lo = 0, hi = 0;
        for (int w : weights) { if (w > lo) lo = w; hi += w; }
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (canShip(weights, mid, days)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
    private boolean canShip(int[] w, int cap, int days) {
        int total = 0, d = 1;
        for (int i = 0; i < w.length; i++) {
            if (total + w[i] > cap) { d++; total = 0; }
            total += w[i];
        }
        return d <= days;
    }
}