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

Solution Approach

Ship packages within d days where each day you load packages in order without exceeding a weight capacity. Find the minimum capacity needed. Use binary search on the capacity range [max(weights), sum(weights)]. For each candidate capacity, simulate loading: iterate through weights, accumulating to the current day's load, and start a new day when adding the next weight would exceed capacity. Count the days needed and compare with d.

function shipWithinDays(weights, d) { var left = Math.max.apply(null, weights); var right = weights.reduce(function(a, b) { return a + b; }, 0); while (left < right) { var mid = Math.floor((left + right) / 2); var days = 1, load = 0; for (var i = 0; i < weights.length; i++) { if (load + weights[i] > mid) { days++; load = 0; } load += weights[i]; } if (days <= d) right = mid; else left = mid + 1; } return left; }

The lower bound is the heaviest single package (must fit on one day). The upper bound is the total weight (all packages in one day). The simulation checks if a given capacity allows shipping within d days by greedily packing as much as possible each day.

Time complexity is O(n log sum), space complexity is 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;
    }
}