Capacity To Ship Packages Within D Days

MediumBinary Searchbinary search on answer

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Packages sit on a conveyor belt in a fixed order; weights[i] is the weight of the i-th package. Each day you load packages onto a ship **in belt order**, stopping before the total would exceed the ship's capacity. Packages cannot be reordered or split. Return the smallest integer ship capacity that lets you ship every package within days days. The capacity must be at least the heaviest package. Aim for O(n log(sum(weights))).

Examples

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
Capacity 15 ships [1,2,3,4,5], [6,7], [8], [9], [10]; capacity 14 needs 6 days.
Input: weights = [3,2,2,4,1,4], days = 3
Output: 6
Ship [3,2], [2,4], [1,4].
Input: weights = [1,2,3,1,1], days = 4
Output: 3
Capacity 3 needs only 3 days ([1,2], [3], [1,1]); capacity 2 cannot carry the package of weight 3.

Constraints

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

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More binary search on answer problems