Problem Description

You have a conveyor belt with packages that need to be shipped within a certain number of days. Each package has a specific weight given in the weights array, where weights[i] represents the weight of the i-th package.

The shipping process works as follows:

• You must load packages onto a ship each day in the exact order they appear on the conveyor belt (you cannot skip or rearrange packages)
• The ship has a weight capacity limit - the total weight of packages loaded on any single day cannot exceed this capacity
• Once you start loading the next day, you begin with a new empty ship

Your task is to find the minimum weight capacity the ship needs to have so that all packages can be shipped within the given number of days.

For example, if weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and days = 5:

• With a ship capacity of 15, you could ship: Day 1: [1,2,3,4,5], Day 2: [6,7], Day 3: [8], Day 4: [9], Day 5: [10]
• This would successfully ship all packages within 5 days

The solution uses binary search to find the minimum capacity. The search range is between:

• Lower bound: The maximum weight among all packages (since the ship must be able to carry at least the heaviest package)
• Upper bound: The sum of all weights (which would allow shipping everything in one day)

The check function determines if a given capacity allows shipping within the required days by simulating the loading process and counting how many days are needed.

Intuition

The key insight is recognizing that this is an optimization problem where we need to find the minimum value (ship capacity) that satisfies a condition (shipping within the given days). When we need to find a minimum or maximum value that satisfies certain constraints, binary search often comes into play.

Think about the relationship between ship capacity and the number of days needed:

• If we increase the ship's capacity, we can load more packages per day, reducing the total days needed
• If we decrease the ship's capacity, we need more days to ship everything
• This creates a monotonic relationship: higher capacity → fewer days, lower capacity → more days

Since there's this clear relationship, we can use binary search on the capacity. But what should our search range be?

The minimum possible capacity must be at least max(weights) because the ship needs to carry the heaviest package. If the capacity is less than this, we can't ship that package at all.

The maximum capacity we'd ever need is sum(weights), which would allow us to ship everything in a single day. Any capacity higher than this would be wasteful.

Now, for any given capacity in this range, we can check if it's feasible by simulating the shipping process:

• Start loading packages in order
• When adding the next package would exceed the capacity, start a new day
• Count the total days needed
• If the days needed ≤ the allowed days, this capacity works

Since we want the minimum capacity that works, we binary search for the leftmost position where the condition is satisfied. The solution cleverly uses bisect_left with a key function that returns True when the capacity is sufficient, effectively finding the minimum viable capacity.

Learn more about Binary Search patterns.

Solution Approach

The solution implements a binary search algorithm to find the minimum ship capacity. Here's how the implementation works:

Binary Search Setup:

• left = max(weights): The minimum possible capacity (must carry the heaviest package)
• right = sum(weights) + 1: One more than the maximum needed capacity (exclusive upper bound for the search range)

The Check Function: The check(mx) function determines if a given capacity mx is sufficient to ship all packages within the allowed days:

def check(mx):
    ws, cnt = 0, 1  # ws: current weight sum, cnt: days used (start with day 1)
    for w in weights:
        ws += w
        if ws > mx:  # Current load exceeds capacity
            cnt += 1  # Start a new day
            ws = w    # Reset weight sum to current package
    return cnt <= days  # Check if we can ship within allowed days

The function simulates the loading process:

• ws tracks the cumulative weight loaded on the current day
• cnt counts the number of days used (initialized to 1 since we start on day 1)
• For each package, we try to add it to the current day's load
• If adding it would exceed capacity mx, we start a new day and put this package as the first item of the new day
• Finally, we return True if the total days needed doesn't exceed the limit

Binary Search Execution:

return left + bisect_left(range(left, right), True, key=check)

This line uses Python's bisect_left function cleverly:

• range(left, right) creates the search space of possible capacities
• key=check transforms each capacity value to a boolean (True if sufficient, False if not)
• Since larger capacities will return True and smaller ones False, we get a pattern like: [False, False, ..., False, True, True, ..., True]
• bisect_left finds the leftmost position where True would be inserted, which is the minimum sufficient capacity
• Adding left to the result gives us the actual capacity value since bisect_left returns an index

The time complexity is O(n * log(sum(weights) - max(weights))) where n is the length of the weights array, as we perform a binary search and each check operation takes O(n) time.

Example Walkthrough

Let's walk through a small example with weights = [3, 2, 2, 4, 1, 4] and days = 3.

Step 1: Determine search boundaries

• left = max(weights) = 4 (ship must carry the heaviest package)
• right = sum(weights) + 1 = 16 + 1 = 17 (upper bound for search)

Step 2: Binary search for minimum capacity

We'll test different capacities to find the minimum that works:

Testing capacity = 4:

• Day 1: Load [3] → total = 3 ✓
  • Try adding 2 → total would be 5 > 4, so start new day
• Day 2: Load [2, 2] → total = 4 ✓
  • Try adding 4 → total would be 8 > 4, so start new day
• Day 3: Load [4] → total = 4 ✓
  • Try adding 1 → total would be 5 > 4, so start new day
• Day 4: Load [1] → total = 1 ✓
  • Try adding 4 → total would be 5 > 4, so start new day
• Day 5: Load [4] → total = 4 ✓

Result: Need 5 days > 3 allowed days ✗

Testing capacity = 6:

• Day 1: Load [3, 2] → total = 5 ✓
  • Try adding 2 → total would be 7 > 6, so start new day
• Day 2: Load [2, 4] → total = 6 ✓
  • Try adding 1 → total would be 7 > 6, so start new day
• Day 3: Load [1, 4] → total = 5 ✓

Result: Need 3 days = 3 allowed days ✓

Binary search process: The actual binary search would proceed as:

• Search range: [4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
• Check results: [F, F, T, T, T, T, T, T, T, T, T, T, T]
• bisect_left finds the first True at index 2
• Minimum capacity = 4 + 2 = 6

Final shipping arrangement with capacity 6:

• Day 1: [3, 2] (weight: 5)
• Day 2: [2, 4] (weight: 6)
• Day 3: [1, 4] (weight: 5)

The minimum ship capacity needed is 6.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n * log(sum(weights) - max(weights)))

The algorithm uses binary search on the range [max(weights), sum(weights)]. The binary search space has a size of sum(weights) - max(weights) + 1, which requires O(log(sum(weights) - max(weights))) iterations.

For each binary search iteration, the check function is called, which iterates through all n elements in the weights array once, taking O(n) time.

Therefore, the overall time complexity is O(n * log(sum(weights) - max(weights))).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space:

• Variables left and right for binary search boundaries
• Variables ws and cnt in the check function
• The check function itself doesn't use recursion or additional data structures

The range(left, right) in bisect_left is a generator in Python 3, which doesn't create the entire list in memory, so it doesn't affect space complexity.

Therefore, the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Day Counting Logic

A frequent mistake occurs when checking if the current load exceeds capacity. Many implementations incorrectly check the condition after adding the weight, leading to improper day counting:

Incorrect Implementation:

def can_ship_with_capacity(capacity):
    current_weight = 0
    days_needed = 1
  
    for weight in weights:
        if current_weight + weight > capacity:  # Check before adding
            days_needed += 1
            current_weight = weight
        else:
            current_weight += weight  # Add only if it fits
          
    return days_needed <= days

Why it's wrong: This approach requires conditional logic to handle whether to add the weight or not, making the code more complex and error-prone.

Correct Implementation:

def can_ship_with_capacity(capacity):
    current_weight = 0
    days_needed = 1
  
    for weight in weights:
        current_weight += weight  # Always add first
      
        if current_weight > capacity:  # Then check if exceeded
            days_needed += 1
            current_weight = weight  # Reset to current package only
          
    return days_needed <= days

Key Insight: By adding first and then checking, we simplify the logic. If the capacity is exceeded, we know the current package must start a new day, so we reset current_weight to just that package's weight.

2. Incorrect Binary Search Bounds

Common Mistake: Setting the lower bound to 1 or 0 instead of max(weights):

# WRONG
min_capacity = 1  # or 0

# CORRECT
min_capacity = max(weights)

Why it matters: If the ship capacity is less than the heaviest package, that package can never be shipped, making the solution impossible. The minimum viable capacity must be at least the weight of the heaviest single package.

3. Forgetting to Initialize Day Count to 1

Incorrect:

days_needed = 0  # Starting with 0 days

Correct:

days_needed = 1  # We start shipping on day 1

Explanation: We begin shipping on day 1, not day 0. Starting with days_needed = 0 would undercount the total days by one, potentially returning an invalid (too small) capacity.

4. Using Inclusive Upper Bound Incorrectly

When using bisect_left with a range, the upper bound should be exclusive:

Incorrect:

max_capacity = sum(weights)
bisect_left(range(min_capacity, max_capacity), ...)  # Excludes sum(weights)

Correct:

max_capacity = sum(weights) + 1  # Add 1 for exclusive upper bound
bisect_left(range(min_capacity, max_capacity), ...)

Why it matters: If the only valid capacity is sum(weights) (shipping everything in one day), the incorrect version would miss this value and could return an incorrect result or cause an error.