Skip to main content

1011. Capacity To Ship Packages Within D Days

medium

Find the minimum ship capacity that delivers all weights, in order, within D days. The textbook 'binary search on the answer' problem after Koko — same template, different domain.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

A conveyor belt has packages that must be shipped from one port to another within days days. The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship. Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.

Constraints

  • 1 <= days <= weights.length <= 5 * 10^4
  • 1 <= weights[i] <= 500

Examples

Example 1

Input
weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output
15

Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this: 1st day: 1, 2, 3, 4, 5; 2nd day: 6, 7; 3rd day: 8; 4th day: 9; 5th day: 10. Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.

Example 2

Input
weights = [3,2,2,4,1,4], days = 3
Output
6

Example 3

Input
weights = [1,2,3,1,1], days = 4
Output
3

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

If capacity c works, every c' > c works too. Monotonic — binary search on the answer.

Hint 2

lo = max(weights) (must fit the heaviest single package); hi = sum(weights) (one mega day).

Hint 3

Feasibility: simulate left-to-right, start a new day when the current day's load would exceed c. Count days; check <= D.

Hint 4

Standard leftmost-true binary search: narrow toward the smallest c that satisfies the feasibility check.

Solution approach

Reveal approach

Binary search on the answer. lo = max(weights) (the ship must at least carry the heaviest package), hi = sum(weights) (worst case, one day). Define canShip(c): simulate a single pass — track currentLoad and dayCount; when adding weights[i] would exceed c, increment dayCount and reset currentLoad to weights[i]; otherwise currentLoad += weights[i]. Return dayCount <= days (start day count at 1 since the simulation begins on day 1). Leftmost-true binary search: while lo < hi, mid = lo + (hi - lo) / 2; if canShip(mid), hi = mid; else lo = mid + 1. Return lo. O(n log(sum)) time, O(1) space. Same template as Koko (LC 875) — recognize the family and you save 5 minutes.

Complexity

Time
O(n log(sum(weights)))
Space
O(1)

Related patterns

  • binary-search
  • binary-search-on-answer

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Goldman Sachs

More Binary Search practice problems

See all Binary Search problems →