LeetCode Problem 1011

Difficulty: 🟡 Medium
Topics: Array, Binary Search

Solution

LeetCode 1011, Capacity To Ship Packages Within D Days

Problem Understanding

This problem asks us to determine the minimum ship capacity required to transport all packages within a fixed number of days.

We are given an array called weights, where weights[i] represents the weight of the i-th package on a conveyor belt. The packages must be shipped in the exact order they appear in the array. This ordering constraint is extremely important because we are not allowed to rearrange packages to make shipping easier.

Each day, the ship can carry packages whose total weight does not exceed the ship's capacity. Once adding another package would exceed the capacity, shipping for that day stops and the remaining packages must wait until the next day.

The goal is to return the smallest possible ship capacity that allows all packages to be shipped within exactly days days or fewer.

The constraints tell us several important things:

• The number of packages can be as large as 5 * 10^4
• Each package weight can be as large as 500
• A naive simulation over every possible capacity could become too slow

Since the input size is large, we need an efficient solution. Any algorithm worse than roughly O(n log n) may struggle with the upper bounds.

There are several important edge cases to keep in mind:

• If days == len(weights), then we can ship one package per day, so the answer is simply the maximum package weight.
• If days == 1, then all packages must be shipped in one day, so the answer is the sum of all weights.
• The ship capacity can never be smaller than the heaviest package, otherwise that package could never be loaded.
• The order restriction prevents greedy rearrangement tricks.

Approaches

Brute Force Approach

A straightforward approach is to try every possible ship capacity starting from the heaviest package weight up to the total sum of all weights.

For each candidate capacity:

1. Simulate the shipping process day by day.
2. Count how many days are needed.
3. Return the first capacity that works within the allowed number of days.

This approach is correct because eventually we will test the optimal capacity. However, it is inefficient because the search range can be very large.

Suppose:

• max(weights) = 500
• sum(weights) can approach 25,000,000

Trying every capacity in that range would be far too slow.

Key Insight

The important observation is that the answer space is monotonic.

If a capacity C is sufficient to ship all packages within days, then any capacity larger than C will also work.

Similarly:

• Small capacities fail
• Large capacities succeed

This creates a classic binary search condition.

Instead of checking every possible capacity, we can binary search over the range:

• Minimum possible capacity = max(weights)
• Maximum possible capacity = sum(weights)

For each midpoint capacity, we simulate shipping and determine whether it works.

If it works:

• Try a smaller capacity

If it fails:

• Try a larger capacity

This reduces the complexity dramatically.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × S)	O(1)	Tries every possible capacity from max weight to total sum
Optimal	O(n log S)	O(1)	Uses binary search on the answer space

Here, n is the number of packages and S is the range of possible capacities.

Algorithm Walkthrough

Step 1: Define the Search Space

The smallest valid capacity is the heaviest package:

left = max(weights)

The largest valid capacity is the sum of all packages:

right = sum(weights)

Any valid answer must lie within this range.

Step 2: Binary Search the Capacity

We repeatedly compute:

mid = (left + right) // 2

This represents a candidate ship capacity.

We then test whether this capacity can ship all packages within the required number of days.

Step 3: Simulate Shipping

To check a capacity:

1. Start with one day.
2. Keep adding packages to the current day's load.
3. If adding a package exceeds capacity:

• Start a new day
• Reset the current load

4. Continue until all packages are processed.

This simulation runs in linear time.

Step 4: Adjust the Search Range

If the simulation uses fewer than or equal to days:

• The capacity works
• Try to minimize further
• Move right = mid

Otherwise:

• The capacity is too small
• Move left = mid + 1

Step 5: Finish the Search

Eventually, left == right.

That value is the minimum valid capacity.

Why it works

The correctness relies on the monotonic property of capacities.

If a capacity works, every larger capacity also works. This guarantees that the valid capacities form a continuous region in the search space. Binary search is therefore valid because we can safely eliminate half the search range after each check.

The simulation itself is greedy but optimal because packages must remain in order. Whenever the current package would exceed the capacity, there is no alternative except starting a new day.

Python Solution

from typing import List

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        def can_ship(capacity: int) -> bool:
            days_needed = 1
            current_load = 0

            for weight in weights:
                if current_load + weight > capacity:
                    days_needed += 1
                    current_load = 0

                current_load += weight

            return days_needed <= days

        left = max(weights)
        right = sum(weights)

        while left < right:
            mid = (left + right) // 2

            if can_ship(mid):
                right = mid
            else:
                left = mid + 1

        return left

The implementation begins by defining a helper function called can_ship. This function determines whether a given ship capacity is sufficient.

Inside the helper function, we simulate the loading process. We maintain:

• days_needed, the number of days used so far
• current_load, the current weight loaded for the day

As we iterate through the packages, we attempt to add each package to the current day's shipment.

If adding a package would exceed the capacity:

• We increment the day count
• Start a new shipment day

At the end, if the total number of days used is within the allowed limit, the capacity is valid.

The main function then performs binary search over the answer space.

The left boundary is initialized to the maximum package weight because no smaller capacity could ever work.

The right boundary is initialized to the total weight because that capacity always works by shipping everything in one day.

The binary search continues shrinking the range until only one valid capacity remains.

Go Solution

func shipWithinDays(weights []int, days int) int {
    canShip := func(capacity int) bool {
        daysNeeded := 1
        currentLoad := 0

        for _, weight := range weights {
            if currentLoad+weight > capacity {
                daysNeeded++
                currentLoad = 0
            }

            currentLoad += weight
        }

        return daysNeeded <= days
    }

    left := 0
    right := 0

    for _, weight := range weights {
        if weight > left {
            left = weight
        }

        right += weight
    }

    for left < right {
        mid := left + (right-left)/2

        if canShip(mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }

    return left
}

The Go implementation follows the exact same algorithmic structure as the Python version.

One small difference is how the binary search midpoint is computed:

mid := left + (right-left)/2

This avoids potential integer overflow, although overflow is not actually a concern under this problem's constraints.

Go slices are used naturally for iterating through package weights, and all variables use integer arithmetic.

Worked Examples

Example 1

weights = [1,2,3,4,5,6,7,8,9,10]
days = 5

Initial search range:

Variable	Value
left	10
right	55

Binary Search Iteration 1

mid = (10 + 55) // 2 = 32

Simulation:

Day	Packages	Total
1	1,2,3,4,5,6,7	28
2	8,9,10	27

Days needed = 2, valid.

Move:

right = 32

Binary Search Iteration 2

mid = (10 + 32) // 2 = 21

Simulation:

Day	Packages	Total
1	1,2,3,4,5,6	21
2	7,8	15
3	9,10	19

Days needed = 3, valid.

Move:

right = 21

Binary Search Iteration 3

mid = (10 + 21) // 2 = 15

Simulation:

Day	Packages	Total
1	1,2,3,4,5	15
2	6,7	13
3	8	8
4	9	9
5	10	10

Days needed = 5, valid.

Move:

right = 15

Binary Search Iteration 4

mid = (10 + 15) // 2 = 12

Simulation requires more than 5 days.

Move:

left = 13

The process continues until:

left = right = 15

Final answer:

15

Example 2

weights = [3,2,2,4,1,4]
days = 3

Initial range:

Variable	Value
left	4
right	16

Testing capacity 6:

Day	Packages	Total
1	3,2	5
2	2,4	6
3	1,4	5

Exactly 3 days are needed, so capacity 6 works.

Testing smaller capacities eventually fails, making 6 the minimum valid answer.

Example 3

weights = [1,2,3,1,1]
days = 4

Initial range:

Variable	Value
left	3
right	8

Testing capacity 3:

Day	Packages	Total
1	1,2	3
2	3	3
3	1,1	2

Only 3 days are needed, which satisfies the requirement.

Testing smaller capacity 2 fails because package 3 cannot fit.

Final answer:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log S)	Binary search performs log S iterations, each requiring a linear scan
Space	O(1)	Only constant extra variables are used

Here:

• n is the number of packages
• S is the search range between max(weights) and sum(weights)

The binary search reduces the number of candidate capacities dramatically, making the solution efficient enough for the input constraints.

Test Cases

from typing import List

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        def can_ship(capacity: int) -> bool:
            days_needed = 1
            current_load = 0

            for weight in weights:
                if current_load + weight > capacity:
                    days_needed += 1
                    current_load = 0

                current_load += weight

            return days_needed <= days

        left = max(weights)
        right = sum(weights)

        while left < right:
            mid = (left + right) // 2

            if can_ship(mid):
                right = mid
            else:
                left = mid + 1

        return left

solution = Solution()

assert solution.shipWithinDays([1,2,3,4,5,6,7,8,9,10], 5) == 15
# official example 1

assert solution.shipWithinDays([3,2,2,4,1,4], 3) == 6
# official example 2

assert solution.shipWithinDays([1,2,3,1,1], 4) == 3
# official example 3

assert solution.shipWithinDays([10], 1) == 10
# single package

assert solution.shipWithinDays([5,5,5,5], 4) == 5
# one package per day

assert solution.shipWithinDays([5,5,5,5], 1) == 20
# all packages in one day

assert solution.shipWithinDays([1,2,3,4,5], 2) == 9
# balanced partition

assert solution.shipWithinDays([7,2,5,10,8], 2) == 18
# classic binary search partition case

assert solution.shipWithinDays([1,1,1,1,1,1,1], 7) == 1
# minimum possible capacity

assert solution.shipWithinDays([100,200,300,400,500], 2) == 900
# large package weights

Test	Why
[1,2,3,4,5,6,7,8,9,10], 5	Verifies the main example
[3,2,2,4,1,4], 3	Tests mixed package grouping
[1,2,3,1,1], 4	Tests near one-package-per-day behavior
[10], 1	Smallest possible input
[5,5,5,5], 4	Capacity equals maximum element
[5,5,5,5], 1	Capacity equals total sum
[1,2,3,4,5], 2	Tests partition balancing
[7,2,5,10,8], 2	Common binary search stress case
[1,1,1,1,1,1,1], 7	Minimal capacity edge case
[100,200,300,400,500], 2	Large values and partitioning

Edge Cases

Edge Case 1: One Package Per Day

Consider:

weights = [5,5,5,5]
days = 4

A common bug is overestimating the required capacity. Since we can ship exactly one package each day, the optimal capacity is simply the largest package weight.

The implementation handles this naturally because the binary search lower bound starts at max(weights).

Edge Case 2: All Packages in One Day

Consider:

weights = [5,5,5,5]
days = 1

In this scenario, the ship must carry every package at once. The required capacity is therefore the total sum.

The algorithm correctly handles this because the upper search bound is initialized to sum(weights), and all smaller capacities fail the simulation.

Edge Case 3: Very Large Single Package

Consider:

weights = [1,1,1,100]
days = 2

A naive implementation might incorrectly allow capacities below 100, even though the package weighing 100 can never fit.

The implementation prevents this by setting:

left = max(weights)

This guarantees that every tested capacity can at least hold the heaviest package.

Edge Case 4: Order Restriction

Consider:

weights = [10,1,1,1,10]
days = 2

Without the order constraint, one might try to balance the loads differently. However, packages must remain in sequence.

The simulation respects the original order exactly by iterating through the array from left to right without rearrangement.