1011. Capacity to Ship Packages Within D Days

Quick Identifier

Topic: binary-search
Pattern: Binary Search (Search on answer)
Difficulty: Medium
Companies: Amazon, Google, Meta, Flexport, Swiggy
Frequency: High
LeetCode: 1011

Quick Sights

Time Complexity: O(n log sum) from the optimal approach.
Space Complexity: O(1) from the optimal approach.
Core Mechanism: Given package weights in order and days, choose a ship capacity (integer) so that items are loaded left-to-right without splitting a package across days, using at most days days. Minimize that capacity.

Given package weights in order and days, choose a ship capacity (integer) so that items are loaded left-to-right without splitting a package across days, using at most days days. Minimize that capacity.

The key is to state the invariant before coding: what part of the input is already settled, what state is still unresolved, and what single operation makes progress without losing correctness.

Recognition cues:

“Minimum capacity / speed / largest chunk” with feasibility check
Loading consecutive groups sums ≤ capacity
Monotone: larger capacity always feasible

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

Brute force — try every capacity from max(weights) to sum(weights) — O(sum * n) worst case.
Better — same check but skip linearly — still slow.
Optimal — O(n log sum) time / O(1) space — binary search capacity; greedily count days needed.

Optimal Solution

Go

func shipWithinDays(weights []int, days int) int {
	maxWeight := 0
	totalWeight := 0
	for _, weight := range weights {
		if weight > maxWeight {
			maxWeight = weight
		}
		totalWeight += weight
	}
	left, right := maxWeight, totalWeight
	for left < right {
		mid := left + (right-left)/2
		if daysNeeded(weights, mid) <= days {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left
}

func daysNeeded(weights []int, capacity int) int {
	days := 1
	running := 0
	for _, weight := range weights {
		if running+weight > capacity {
			days++
			running = weight
		} else {
			running += weight
		}
	}
	return days
}

JavaScript

function shipWithinDays(weights, daysLimit) {
	let maxWeight = 0;
	let totalWeight = 0;
	for (const weight of weights) {
		maxWeight = Math.max(maxWeight, weight);
		totalWeight += weight;
	}
	let left = maxWeight;
	let right = totalWeight;
	while (left < right) {
		const mid = left + Math.floor((right - left) / 2);
		if (daysNeeded(weights, mid) <= daysLimit) {
			right = mid;
		} else {
			left = mid + 1;
		}
	}
	return left;
}

function daysNeeded(weights, capacity) {
	let days = 1;
	let running = 0;
	for (const weight of weights) {
		if (running + weight > capacity) {
			days++;
			running = weight;
		} else {
			running += weight;
		}
	}
	return days;
}