LeetCode · #1011

Capacity To Ship Packages Within D Days Solution

Find the minimum ship capacity that lets us deliver all packages in order within a fixed number of days.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #1011

🏗️

Pattern

Binary Search — search on answer

Packages must stay in their original order. If the ship capacity is C, we greedily load as many consecutive packages as fit each day. We want the smallest capacity whose simulation finishes within days.

Example

Input:  weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
// Capacity 15 works:
// Day1: 1+2+3+4+5 = 15
// Day2: 6+7 = 13
// Day3: 8
// Day4: 9
// Day5: 10

Section Two · Approach 1

Test Every Capacity — O(n · sum(weights))

We could try capacities starting from max(weights) upward, simulate shipping for each, and return the first one that works.

Problem: The answer range can be huge. But the feasibility is monotonic: if capacity C works, every larger capacity also works. That monotonic boundary is exactly what binary search needs.

Section Three · Approach 2

Binary Search on Capacity — O(n log(sum-max))

The minimum possible capacity is max(weights) because the heaviest package must fit. The maximum possible capacity is sum(weights) because one day could carry everything. Binary search that interval and use a greedy simulation as the feasibility function.

💡 Mental model: Think of capacity as a volume knob. Too low means you need too many days. High enough means the schedule fits. Binary search locates the first knob setting where the schedule becomes feasible.

Search space: [max(weights), sum(weights)]
Feasibility check: greedily pack consecutive weights until the next one would overflow capacity, then start a new day
If the days used are <= days, the capacity is feasible
Feasible → search left for a smaller capacity
Infeasible → search right for a larger capacity

Recognition signal:

“Minimum capacity / speed / rate / threshold such that a greedy simulation works” is the classic binary-search-on-answer pattern.
Write the monotonic check first, then search the answer space.

Section Four · Trace

Visual Walkthrough

Trace the sample input.

LC 1011 — binary search on ship capacity

Section Five · Implementation

Code — Java & Python

Java — binary search + greedy day counter

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int left = 0, right = 0;
        for (int weight : weights) {
            left = Math.max(left, weight);
            right += weight;
        }

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canShip(weights, days, mid)) right = mid;
            else left = mid + 1;
        }

        return left;
    }

    private boolean canShip(int[] weights, int days, int capacity) {
        int usedDays = 1;
        int current = 0;

        for (int weight : weights) {
            if (current + weight > capacity) {
                usedDays++;
                current = 0;
            }
            current += weight;
        }

        return usedDays <= days;
    }
}

Python — search the first feasible capacity

class Solution:
    def shipWithinDays(self, weights: list[int], days: int) -> int:
        left, right = max(weights), sum(weights)

        def can_ship(capacity: int) -> bool:
            used_days = 1
            current = 0
            for weight in weights:
                if current + weight > capacity:
                    used_days += 1
                    current = 0
                current += weight
            return used_days <= days

        while left < right:
            mid = (left + right) // 2
            if can_ship(mid):
                right = mid
            else:
                left = mid + 1

        return left

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Test every capacity	O(n · sum(weights))	O(1)	Too slow when the answer range is large.
Binary search on answer ← optimal	O(n log(sum(weights) - max(weights)))	O(1)	Each candidate capacity is checked with one greedy scan.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Expected behavior	Why it matters
One package heavier than capacity	Impossible for that capacity	This is why the lower bound is `max(weights)`.
`days == 1`	Answer is `sum(weights)`	Everything must ship together.
`days == weights.length`	Answer is `max(weights)`	You can ship at most one package per day.
Reordering packages	Not allowed	The greedy simulation must preserve the original order.
Feasible mid	Search left	We need the minimum feasible capacity, not any feasible capacity.

⚠ Common Mistake: Resetting the day count incorrectly or trying to sort the weights. The order is fixed, so the only valid simulation is one left-to-right pass that starts a new day exactly when the next package would overflow the ship.

← Back to Binary Search problems

LearningTree

LC 1011 · Capacity To Ship Packages Within D Days — Solution & Explanation | DSA Guide