1011. Capacity to Ship Packages Within D Days

At a Glance

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

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.

Recognition Cues

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

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

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;
}