DSA interview question

Capacity to Ship Packages Within D Days

Medium · Algorithms · Topics: binary search on answer, array, greedy

The problem

A courier company loads packages onto one ship per day, in the order they arrived: it can't reorder them, only decide where each day's load ends. Every package must ship within D days. What's the smallest ship capacity that makes this possible? A bigger ship never needs more days, so feasibility is monotonic in the capacity. The capacity must be at least the heaviest package (or it could never ship) and never needs to exceed the total weight (everything in one day). Binary search between those, with a greedy day count as the check.

Example: weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], D = 5 → 15.

Function signature

int shipWithinDays(const vector<int>& weights, int days);

Test cases

Input `(weights, days)`	Output	Explanation
`([1..10], 5)`	15	[1,2,3,4,5], [6,7], [8], [9], [10]
`([3, 2, 2, 4, 1, 4], 3)`	6	[3,2], [2,4], [1,4]
`([1, 2, 3, 1, 1], 4)`	3	[1], [2], [3], [1,1]
`([10], 1)`	10
`([1, 1, 1, 1], 4)`	1	One package a day

(Confirm: packages ship in the given order; a day's load can't exceed the capacity; days ≤ number of packages.)

How interviewers phrase it

"Find the least ship capacity that ships all packages within D days" (LeetCode 1011).
The same structure as book allocation, painter's partition and split array largest sum.

Clarifying questions to ask

Must packages ship in the given order?
Can a day be empty? (It doesn't matter: fewer days is also fine.)
How large are the weights? (The total needs 64 bits for big inputs.)

Follow-ups to expect

"What's the search range?"
"How do you count days for a capacity?"
"Why is greedy loading optimal?"
"Why can you accept daysNeeded ≤ D rather than == D?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview