Capacity To Ship Packages Within D Days

Capacity To Ship Packages Within D Days

What is this problem about?

The Capacity To Ship Packages Within D Days interview question is a classic optimization problem. You have a conveyor belt with packages of different weights that must be shipped in the order given. You have a ship that can carry a maximum weight (capacity). You need to find the least weight capacity of the ship that will allow all packages to be shipped within D days. This Capacity To Ship Packages Within D Days coding problem is a search for a minimum threshold.

Why is this asked in interviews?

This is a high-frequency question at companies like Apple, Google, and Amazon. It tests if a candidate can recognize that the answer lies within a specific range and that the condition is "monotonic"—meaning if capacity X works, then X+1 also works. This realization allows you to use Binary Search on the Answer, an essential technique for optimization problems.

Algorithmic pattern used

This problem utilizes the Array, Binary Search interview pattern.

1. Define Search Range: Minimum capacity must be max(weights) (can't ship the heaviest package otherwise). Maximum capacity is sum(weights) (ship everything in 1 day).
2. Binary Search: Pick a middle capacity mid.
3. Verification: Check if it's possible to ship everything in D days using mid capacity by greedily filling the ship each day.
4. If it works, try a smaller capacity; otherwise, try a larger one.

Example explanation

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

• Low = 10, High = 55.
• Try mid = 32. Can we ship in 5 days?
  • Day 1: 1+2+3+4+5+6+7 = 28 (next is 8, total 36 > 32).
  • Day 2: 8+9+10 = 27.
  • Done in 2 days. 32 works!
• Now search range [10, 31]. Continue until the smallest valid capacity is found (which is 15).

Common mistakes candidates make

• Linear Search: Trying every capacity from 1 upwards, which is too slow (O(N * Sum)).
• Incorrect Boundaries: Starting the low pointer at 1 instead of the maximum single package weight.
• Verification Logic: Not correctly handling the order of packages—packages must be shipped in the given order.

Interview preparation tip

Master "Binary Search on the Answer." If you are asked to find the "minimum maximum" or "maximum minimum" of something, and you can write a simple "check" function to see if a value is valid, binary search is likely the optimal approach.