Domain 2MediumMEDIUM

Capacity To Ship Packages Within D Days

LeetCode problem 1011: Capacity To Ship Packages Within D Days (medium).

Domain: medium•Updated: 2026-09-06
#Array#Binary Search

Problem Breakdown

We are given a list of package weights and a target number of days (D). We need to determine the minimum ship capacity required so that all packages can be shipped within those D days while maintaining their original order on the conveyor belt.

Key constraints:

  1. Packages cannot be reordered; they must form contiguous subarrays for each day’s shipment.
  2. The sum of weights in any single day’s load cannot exceed the ship capacity.

Inputs:

  • weights: List of integers representing package weights.
  • D: Integer representing maximum days allowed.

Outputs:

  • An integer representing the minimum required capacity.

Implicit constraints & Edge cases to consider:

  1. Minimum Capacity Bound: The capacity must be at least equal to the heaviest single package (max(weights)). If a ship is smaller than one specific weight, it’s impossible regardless of days.
  2. Maximum Capacity Bound: In the worst case (shipping everything in 1 day), the capacity equals sum(weights).
  3. Ordering Constraint: We cannot skip packages or reorder them; this simplifies simulation but prevents simple greedy sorting approaches.

Intuition

A brute-force approach would be to iterate through every possible integer value for ship capacity from max(weights) up to sum(weights), and for each, simulate the shipping process to see if it fits in D days. This is inefficient because the range of capacities can be very large (up to 5⋅104×500=2.5⋅1075 \cdot 10^4 \times 500 = 2.5 \cdot 10^7).

However, observe a monotonic property:

  • If a capacity C allows us to ship within D days, then any capacity C' > C will also work (it might take fewer or the same number of days).
  • Conversely, if C is too small and takes more than D days, we need a larger capacity.

This monotonicity allows us to use Binary Search on the Answer Space. We search for the smallest valid capacity within the range [max(weights), sum(weights)]. This reduces our complexity significantly compared to linear iteration over capacities.

Approach

  1. Initialize left bound as max(weights) and right bound as sum(weights). These represent the absolute minimum possible answer (must carry heaviest item) and maximum necessary capacity (carry all at once).
  2. Perform a binary search loop while left <= right:
    • Calculate mid = left + (right - left) // 2 to avoid overflow issues in other languages, though Python handles large ints automatically.
  3. Simulation Function: For each candidate capacity (mid), simulate the shipping process:
    • Initialize a counter for days used and current day’s load sum.
    • Iterate through weights. Add weight to current load.
    • If adding this weight exceeds mid, increment the day count, reset current load to just that new package (since we can’t split packages).
  4. Decision Logic:
    • If simulated days used ≤D\le D: This capacity is feasible. We try a smaller one for optimization (right = mid - 1). Store mid as potential answer or simply set the search range to find the minimum valid value (typically we store result when moving right, but here since we want min, if feasible we move left).
    • If simulated days used >D> D: Capacity is too small. We need more (left = mid + 1).
  5. Return right or stored answer after loop terminates. Note: In standard binary search for minimum valid value where condition holds on right side, usually we return the last feasible found or simply use logic to narrow down until left == left. A common pattern is returning left when left > right because if a solution exists (which it always does within bounds), left will converge to the smallest valid capacity.

Complexity Analysis

  • Time Complexity: O(N⋅log⁡(∑W))O(N \cdot \log(\sum W)).
    • We perform binary search over the range of possible capacities, which is bounded by the sum of weights (SS). The number of iterations is log⁡(S)\log(S).
    • Inside each iteration, we iterate through all N packages to simulate shipping.
    • Given constraints N≤50,000N \le 50,000, this fits well within time limits (typically ~1 second for Python allows roughly 10710^7 ops).
  • Space Complexity: O(1)O(1). We only use a few variables (left, right, mid, counters) regardless of input size.

Solution

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        # Lower bound is the heaviest single package (cannot split packages).
        left = max(weights) 
        # Upper bound is shipping everything in one day.
        right = sum(weights) 
        
        while left < right:
            mid = (left + right) // 2
            
            # Check if capacity 'mid' can ship within D days
            current_load = 0
            days_needed = 1 
            
            for w in weights:
                current_load += w
                
                # If adding this package exceeds capacity, start a new day
                if current_load > mid:
                    days_needed += 1
                    current_load = w
            
            # Optimization check: 
            # We need to ship within D days.
            # If we used fewer or equal days than allowed (days_needed <= D),
            # then 'mid' is feasible, and potentially smaller capacities might work too.
            if days_needed > D:
                left = mid + 1
            else:
                right = mid
                
        return left

Edge Cases Handled

  • Single Package: If weights has one element, left == max(weights), loop logic handles it correctly (returns that weight).
  • D equals Length of Weights: The simulation will naturally assign 1 day per package if capacity is tight enough. Binary search finds the minimum to satisfy this constraint.
  • Large Sum / Overflow: Python integers handle arbitrary size, so sum(weights) won’t overflow standard types like in C++/Java (though logic remains valid).
  • Capacity Tightness: The simulation resets load correctly when a package alone exceeds capacity? No, wait: the lower bound ensures mid >= max(weights), so no single package will ever exceed mid inside the loop. This prevents invalid states where one item can’t fit at all.