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.

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. Using Wrong Binary Search Template Variant

A common mistake is using while left < right with right = mid, which is a different binary search variant:

# WRONG - different template variant
while left < right:
    mid = (left + right) // 2
    if feasible(mid):
        right = mid
    else:
        left = mid + 1
return left

Correct template:

first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if feasible(mid):
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1
return first_true_index

The template explicitly tracks the answer with first_true_index, uses while left <= right, and always moves right = mid - 1 when the condition is true.

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

A frequent mistake occurs when checking if the current load exceeds capacity:

Incorrect Implementation:

def feasible(capacity):
    current_weight = 0
    days_needed = 1

    for weight in weights:
        if current_weight + weight > capacity:
            days_needed += 1
            current_weight = weight
        else:
            current_weight += weight

    return days_needed <= days

Correct Implementation:

def feasible(capacity):
    current_weight = 0
    days_needed = 1

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

    return days_needed <= days

By adding first and then checking, the logic is simpler: if capacity is exceeded, the current package starts a new day.

3. Incorrect Binary Search Bounds

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

# WRONG
left = 1  # or 0

# CORRECT
left = max(weights)

The ship must carry at least the heaviest package.

4. Forgetting to Initialize Day Count to 1

# WRONG
days_needed = 0

# CORRECT
days_needed = 1

We begin shipping on day 1, not day 0.