LeetCode #1011 Medium

Capacity to Ship Packages Within D Days

Packages must ship in their given order. Each day the ship loads packages in sequence without exceeding its capacity. Find the minimum capacity that ships everything within days days.

binary-searcharraybinary-search-on-answergreedy

Open on LeetCode ↗

02

Intuition

💡

This is the same shape as Koko: we cannot compute the capacity directly, but given a candidate we can greedily simulate the loading in one pass and count the days used. Larger capacity never needs more days, so feasibility is monotonic and binary search applies to the capacity itself. The one difference worth noting is the lower bound: capacity must be at least max(weights), because a package heavier than the ship can never be loaded at all.

03

Approach

1

Fix the search bounds carefully

The upper bound is sum(weights) — with that capacity everything ships on day one. The lower bound is not 1: it is max(weights), since a single package heavier than the ship's capacity is unshippable no matter how many days are available. Getting this bound wrong is the classic mistake here; starting at 1 wastes probes and, if the feasibility check does not explicitly reject oversized packages, produces wrong answers.

2

Check a candidate greedily

Given a capacity, walk the packages in order accumulating weight. When the next package would overflow the current day's load, start a new day and put it there. This greedy is optimal because the order is fixed — deferring a package that fits today can never reduce the total number of days. Count the days and compare with the limit.

3

Binary search on capacity

Probe the midpoint of [max(weights), sum(weights)]. If the greedy fits within days, record it and search lower for a tighter ship. If it needs too many days, search higher. The crossing point is the minimum feasible capacity. O(n log sum) overall.

04

Solution & live demo

python

▶1class Solution:
▶2    def shipWithinDays(self, weights, days):
▶3        lo, hi, best = max(weights), sum(weights), -1
▶4        while lo <= hi:
▶5            cap = (lo + hi) // 2
▶6            used, load = 1, 0
▶7            for w in weights:
▶8                if load + w > cap:
▶9                    used += 1
▶10                    load = w
▶11                else:
▶12                    load += w
▶13            if used <= days:
▶14                best = cap
▶15                hi = cap - 1
▶16            else:
▶17                lo = cap + 1
▶18        return best

05

Edge cases

days == 1

The answer is sum(weights) — the top of the search range. Every smaller capacity needs at least two days.

days == number of packages

Each package gets its own day, so the answer is max(weights) — the bottom of the range.

One package much heavier than the rest

It alone forces the lower bound. The search cannot return anything below it, which is exactly why the range starts at max(weights).

days exceeds the package count

The extra days are simply unused; the answer is still max(weights).

06

Complexity

Time

O(n log sum(weights))

Space

O(1)

The greedy simulation is O(n) per probe and the range spans at most the total weight, giving roughly 30 probes for realistic inputs.