Packages with the given weights must be shipped in order, one ship per day, and a day's load can't exceed the ship's capacity. Return the least capacity that ships everything within the given number of days.
Before you code
Checking a given capacity is easy: load packages greedily until the next one doesn't fit, then start a new day. If a capacity works, a bigger one works too. That is all binary search needs.
Hints
- Lower bound: the heaviest package (it must fit on its own). Upper bound: the total weight (one day).
days_needed(c): walk the weights, starting a new day whenever the current load plus the next package exceeds c.- Search for the first c with
days_needed(c) <= days.
Production & complexity notes
When solving Capacity to ship packages within D days on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Searching an answer space to reinforce the underlying pattern.
What it practices
Choosing safe bounds and a monotonic check, from Searching an answer space.