Warning: This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#1011) before relying on it.

🚢 Capacity To Ship Packages Within D Days

An interactive visualization of how binary search finds the minimum ship capacity. Watch the algorithm partition packages into daily shipments step by step.

Binary Search LeetCode 1011 ↗ Medium

The Problem

A conveyor belt has packages that must be shipped from one port to another within days days.

The i-th package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages in the order given by the conveyor belt (we cannot skip or reorder packages). We must not load more weight than the maximum capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages being shipped within days days.

Interactive Visualization

Weights (comma-separated)

Days

Preset

Speed:

Packages

Binary Search Range

mid (cap)

—

Current Step

Press Step or Play to begin.

Code

fun shipWithinDays(weights: IntArray, days: Int): Int {    var lo = weights.max()    var hi = weights.sum()    while (lo < hi) {        val mid = (lo + hi) / 2        var ships = 1        var current = 0        for (w in weights) {            if (current + w > mid) {                ships++                current = 0            }            current += w        }        if (ships <= days)       // can ship → try smaller            hi = mid        else                     // too many ships → need more            lo = mid + 1    }    return lo  // minimum valid capacity}

def shipWithinDays(weights, days):    lo = max(weights)    hi = sum(weights)    while lo < hi:        mid = (lo + hi) // 2        ships = 1        current = 0        for w in weights:            if current + w > mid:                ships += 1                current = 0            current += w        if ships <= days:  # can ship → try smaller            hi = mid        else:            # too many ships → need more            lo = mid + 1    return lo  # minimum valid capacity

How It Works

Key Insight

The ship capacity has a monotonic property: if we can ship all packages within days days using capacity c, we can also do it with any capacity greater than c. This makes it a perfect candidate for binary search on the answer.

The Algorithm

Search space: lo = max(weights) (must be able to carry the heaviest single package), hi = sum(weights) (ship everything in one day)
Each iteration: try the middle capacity mid = (lo + hi) // 2
Simulate shipping: greedily load packages in order onto each ship. When adding the next package would exceed mid, start a new ship (new day).
If feasible (ships needed ≤ days): we might get by with less capacity → hi = mid
If not feasible: we need more capacity → lo = mid + 1
When lo = hi: we have found the minimum valid capacity

Complexity

Time O(n * log(sum - max))

Space O(1)

We do log(sum(weights) - max(weights)) binary search iterations, and each iteration scans all n packages to simulate the greedy loading.