Capacity to Ship Packages

📋

Problem

Imagine you are managing a shipping company that needs to send packages across several days. You want to find the minimum ship capacity that allows all packages to be shipped within a given number of days.

You are given an array weights where weights[i] is the weight of the i-th package, and an integer days representing the number of days to ship all packages. Each day, you load the ship with packages in order without exceeding the ship's capacity. Return the minimum capacity of the ship such that all packages can be shipped within days.

1 ≤ weights.length ≤ 10^51 ≤ weights[i] ≤ 5001 ≤ days ≤ weights.length

Edge cases: All packages have the same weight → output is that weightdays equals the number of packages → output is max package weightdays equals 1 → output is sum of all weights

</>

IDE

def ship_with_capacity(weights: list[int], days: int) -> int:public int shipWithCapacity(int[] weights, int days)int shipWithCapacity(vector<int> &weights, int days)function shipWithCapacity(weights, days)

def ship_with_capacity(weights, days):
    # Write your solution here
    pass

class Solution {
    public int shipWithCapacity(int[] weights, int days) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int shipWithCapacity(vector<int> &weights, int days) {
    // Write your solution here
    return 0;
}

function shipWithCapacity(weights, days) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: sum(weights)Always returning sum of weights regardless of days, ignoring feasibility checks.✅ Implement binary search on capacity and use feasibility function to find minimal capacity.

Wrong: max(weights)Returning max weight without considering days less than number of packages.✅ Use feasibility function to check if capacity max(weights) suffices for given days; if not, increase capacity.

Wrong: Incorrect capacity due to greedy sorting of packagesSorting packages and shipping largest first breaks order constraint.✅ Preserve package order in feasibility check; do not sort weights array.

Wrong: Off-by-one errors in binary search leading to capacity too low or too highIncorrect mid calculation or loop condition in binary search.✅ Use inclusive binary search with while left < right and mid = (left + right) // 2; update boundaries correctly.

Wrong: TLE on large inputsUsing brute force or naive approach with O(n * S) complexity.✅ Implement binary search on answer space with O(n log S) feasibility checks.

✓

Test Cases

Focus on handling boundary conditions like single package and days equal to array length.

Watch out for common algorithmic traps like greedy sorting and off-by-one errors in binary search.

Optimize your solution to O(n log S) using binary search on the answer space to handle large inputs efficiently.

t1_01basic

Input{"weights":[1,2,3,4,5,6,7,8,9,10],"days":5}

Expected15

⏱ Performance - must finish in 2000ms

One optimal way is to ship packages in groups: [1,2,3,4,5], [6,7], [8], [9], [10]. The ship capacity must be at least 15 to ship all packages in 5 days.

💡 Think about binary searching the ship capacity between max package weight and sum of all weights.

💡 Use a feasibility function to check if a given capacity can ship all packages within the given days.

💡 Implement binary search on capacity and use the feasibility check to narrow down the minimum capacity.

Why it failed: Failed basic case: likely incorrect feasibility check or binary search boundaries. Fix by ensuring feasibility counts days correctly and binary search uses inclusive bounds.

✓ Correctly implements binary search on answer space with proper feasibility check.

t1_02basic

Input{"weights":[3,2,2,4,1,4],"days":3}

Expected6

⏱ Performance - must finish in 2000ms

One optimal way is to ship packages in groups: [3,2], [2,4], [1,4]. Minimum capacity is 6.

💡 Check the feasibility of capacity 6 by simulating shipping days.

💡 Remember to reset current load when capacity exceeded and increment day count.

💡 Binary search between max weight (4) and sum (16) to find minimum capacity.

Why it failed: Incorrect output due to off-by-one error in feasibility or binary search loop. Fix by carefully updating day count and capacity checks.

✓ Correctly finds minimum capacity using binary search and feasibility function.

t2_01edge

Input{"weights":[5,5,5,5,5],"days":5}

Expected5

⏱ Performance - must finish in 2000ms

Each package must be shipped on its own day; capacity must be at least the max package weight 5.

💡 When days equals number of packages, capacity must be at least max weight.

💡 Feasibility check should allow exactly one package per day in this case.

💡 Minimum capacity equals max(weights) when days == len(weights).

Why it failed: Fails edge case where days == number of packages; likely sums multiple packages per day incorrectly. Fix feasibility to count days properly.

✓ Correctly handles case where days equals number of packages.

t2_02edge

Input{"weights":[10],"days":1}

Expected10

⏱ Performance - must finish in 2000ms

Only one package and one day; capacity must be the package weight 10.

💡 Single package means capacity must be at least that package's weight.

💡 Feasibility check should handle single-element arrays correctly.

💡 Minimum capacity equals the single package weight when only one package.

Why it failed: Fails single package case; possibly incorrect initialization or boundary checks. Fix by handling single-element arrays properly.

✓ Correctly handles single package input.

t2_03edge

Input{"weights":[1,2,3,4,5],"days":1}

Expected15

⏱ Performance - must finish in 2000ms

Only one day to ship all packages; capacity must be sum of all weights 15.

💡 When days is 1, capacity must be sum of all weights.

💡 Feasibility check should confirm capacity can hold all packages in one day.

💡 Minimum capacity equals sum(weights) when days == 1.

Why it failed: Fails single day case; feasibility may incorrectly split packages. Fix feasibility to allow all packages in one day if capacity permits.

✓ Correctly handles single day shipping case.

t3_01corner

Input{"weights":[1,2,3,1,1],"days":2}

Expected5

⏱ Performance - must finish in 2000ms

Greedy approach that always picks largest packages first fails; correct minimum capacity is 5.

💡 Greedy approach picking largest packages first may fail here.

💡 Use binary search with feasibility function that respects package order.

💡 Check feasibility by simulating sequential loading, not by sorting packages.

Why it failed: Fails greedy trap: sorting packages breaks order constraint. Fix by preserving package order in feasibility check.

✓ Correctly handles package order and avoids greedy trap.

t3_02corner

Input{"weights":[10,10,10,10],"days":2}

Expected20

⏱ Performance - must finish in 2000ms

Confusing 0/1 vs unbounded knapsack: each package must be shipped once in order; capacity 20 allows two packages per day.

💡 Each package can only be shipped once and in order.

💡 Feasibility function must count days correctly without reusing packages.

💡 Minimum capacity is max weight * (packages per day) respecting order.

Why it failed: Fails 0/1 constraint: allowing multiple shipments of same package or ignoring order. Fix feasibility to count packages once in order.

✓ Correctly enforces 0/1 shipment and order constraints.

t3_03corner

Input{"weights":[1,2,3,4,5,6,7,8,9,10],"days":3}

Expected18

⏱ Performance - must finish in 2000ms

Off-by-one error in binary search boundaries leads to incorrect capacity; correct minimum capacity is 18.

💡 Check binary search mid calculation and loop conditions.

💡 Ensure feasibility check uses <= days, not < days.

💡 Adjust binary search to include both ends of capacity range.

Why it failed: Fails due to off-by-one in binary search or feasibility condition. Fix by using inclusive bounds and correct day count comparison.

✓ Correctly implements binary search with proper boundaries.

t4_01performance

Input{"weights":[500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1,500,1],"days":50}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, weights alternate between 500 and 1, days=50. O(n log S) solution must complete within 2 seconds.

💡 Binary search on capacity with O(n log S) complexity is required.

💡 Brute force checking all capacities is O(n * S) and will time out.

💡 Use feasibility function with early stopping to speed up checks.

Why it failed: TLE due to brute force or naive approach with O(n * S) complexity. Fix by implementing binary search on answer space with O(n log S) feasibility checks.

✓ Efficient O(n log S) solution confirmed by passing performance test.

Practice

1. You are given a sorted array where every element appears exactly twice except for one element which appears only once. Which algorithmic approach guarantees an optimal O(log n) time solution to find the single element?

easy

A. Modified binary search using index parity to halve the search space

B. Dynamic programming to store counts of elements and find the unique one

C. Linear scan checking pairs sequentially until the unique element is found

D. Greedy approach selecting elements based on local pair matches

Solution

1. Step 1: Understand problem constraints

   The array is sorted and every element except one appears twice consecutively.

2. Step 2: Identify algorithm that exploits sorted pairs

   Modified binary search using index parity halves the search space by comparing pairs, achieving O(log n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search with parity is known optimal for this problem [OK]

Hint: Use parity-based binary search for O(log n) solution [OK]

Common Mistakes:

• Thinking linear scan is optimal
• Using DP unnecessarily
• Applying greedy without global insight

2. Consider the following buggy code for finding a peak element. Which line contains the subtle bug that can cause incorrect results or infinite recursion?

def findPeakElement(nums):
    def binarySearch(low, high):
        if low == high:
            return low
        mid = (low + high) // 2
        if nums[mid] < nums[mid]:  # Line X
            return binarySearch(mid + 1, high)
        else:
            return binarySearch(low, mid)
    return binarySearch(0, len(nums) - 1)

medium

A. Line 5: if nums[mid] < nums[mid]:

B. Line 4: mid = (low + high) // 2

C. Line 3: if low == high: return low

D. Line 7: return binarySearch(low, mid)

Solution

1. Step 1: Identify suspicious comparison

   Line 5 compares nums[mid] with itself, which is always false, causing wrong recursion path.

2. Step 2: Understand impact

   This bug causes infinite recursion or incorrect peak detection because the condition never triggers correctly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Comparison must be nums[mid] < nums[mid + 1] [OK]

Hint: Check comparisons carefully for off-by-one errors [OK]

Common Mistakes:

• Comparing mid with mid instead of mid+1
• Off-by-one causing infinite recursion
• Returning wrong index after recursion

3. What is the time complexity of the binary search on value range approach to find the median of two sorted arrays of sizes m and n, where the arrays contain values in the range [minVal, maxVal]?

medium

A. O(m + n)

B. O(log(m + n))

C. O((m + n) * log(maxVal - minVal))

D. O(log(maxVal - minVal) * (log m + log n))

Solution

1. Step 1: Identify outer binary search complexity

   Binary search on value range runs in O(log(maxVal - minVal)) iterations.

2. Step 2: CountLessEqual calls cost

   Each countLessEqual uses bisect on both arrays, each O(log m) and O(log n), total O(log m + log n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Nested binary searches multiply complexities [OK]

Hint: Outer binary search times bisect calls per iteration [OK]

Common Mistakes:

• Confusing with merge O(m+n)
• Assuming O(log(m+n)) without value range
• Ignoring bisect cost inside loop

4. Examine the following buggy code for finding the single non-duplicate element in a sorted array. Which line contains the subtle bug that can cause incorrect results or infinite loops?

medium

A. Line 11: updating high to mid - 1 may skip the single element

B. Line 5: parity check on mid is incorrect for odd indices

C. Line 7: comparison with nums[mid + 1] can cause index out of range

D. Line 3: mid calculation uses division without floor, resulting in float index

Solution

1. Step 1: Identify mid calculation issue

   Using '/' in Python 3 returns float, which cannot index arrays, causing errors or infinite loops.

2. Step 2: Confirm other lines are correct

   Parity checks and updates are correct; no out-of-range access due to loop conditions.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   mid must be integer index; float causes failure [OK]

Hint: mid must be integer index, not float [OK]

Common Mistakes:

• Using '/' instead of '//' in Python 3
• Confusing parity logic
• Incorrect boundary updates

5. Suppose the problem is modified so that the array is sorted but the single element can appear multiple times (not necessarily once), and all other elements appear exactly twice. Which modification to the binary search approach correctly finds the single element?

hard

A. Modify binary search to compare mid with neighbors and adjust search space based on counts of duplicates around mid

B. Switch to linear scan because binary search parity logic breaks when single element repeats

C. Use the same parity-based binary search since duplicates still appear in pairs

D. Use a hash map to count occurrences since binary search can't handle multiple single elements

Solution

1. Step 1: Understand problem change

   The single element may appear multiple times, breaking the strict pair pattern.

2. Step 2: Analyze binary search adaptation

   Parity-based halving fails; instead, compare mid with neighbors and count duplicates to decide which half to search.

3. Step 3: Confirm other options

   Linear scan is inefficient; hash map uses extra space and is unnecessary if modified binary search works.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Counting duplicates around mid guides correct binary search [OK]

Hint: Modify binary search to handle variable duplicate counts [OK]

Common Mistakes:

• Assuming parity logic still works
• Switching to linear scan prematurely
• Using extra space unnecessarily