AlgoViz
HomeBinary Search

Minimum Shipping Capacity

Medium

The same capacity search

Problem

Packages on a conveyor must ship in order within d days. A ship has a fixed daily weight capacity. Return the least capacity that ships every package within d days.

In simple words

More capacity means fewer days — binary-search the smallest ship that still finishes in time.

The idea

Identical structure: the daily weight limit is the thing being searched, and a greedy pass counts how many days that limit needs. Because more capacity never costs more days, binary search applies.

The trick

  • Search range: max(weights) to sum(weights).
  • Packages must ship in order, which is what makes the greedy count correct.
5
6
7
8
9
10
11
12
13
14
15
0
1
2
3
4
5
6
7
8
9
10
candidates11

Step 1 of 4. Brute force: try every ship capacity until the load fits in 3 days. Values: 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15. candidates 11.

1/4
Brute force
timeO(sum·n)spaceO(1)

Try every capacity.

1let best = -1;2for (let cap = maxW; cap <= sum && best < 0; cap++)3  if (daysNeeded(cap) <= days) best = cap;4return best;

Input

array
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

Memory

try
—
candidates
11
capacity
—

Output

capacity
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5
Output:
15
Explanation:
A ship of size 15 finishes in 5 days.

Example 2

Input:
weights = [3, 2, 2, 4, 1, 4], days = 3
Output:
6
Explanation:
Capacity 6 splits the load into 3 days.

Example 3

Input:
weights = [1, 2, 3, 1, 1], days = 4
Output:
3
Explanation:
Capacity 3 fits in 4 days.

Constraints

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

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.