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 and a target number x. The task is to find k elements closest to x in the array, with ties broken by choosing the smaller elements first. Which of the following approaches guarantees an optimal solution with logarithmic search complexity on the array?

easy

A. Use a greedy approach by iteratively picking the closest element to x until k elements are chosen.

B. Use dynamic programming to compute the minimum distance sum for all windows of size k and pick the minimum.

C. Perform a binary search to find the left boundary of the window of size k that contains the closest elements to x.

D. Use a two-pointer sliding window starting from both ends of the array and shrink towards the center until k elements remain.

Solution

1. Step 1: Understand problem constraints

   The array is sorted, and we want k closest elements to x with tie-breakers favoring smaller elements.

2. Step 2: Identify approach with logarithmic complexity

   Binary search on the left boundary of the window of size k efficiently narrows down the candidate window in O(log(n-k)) time, guaranteeing optimality.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Binary search exploits sorted order and window size constraints [OK]

Hint: Binary search on window boundaries exploits sorted array [OK]

Common Mistakes:

• Assuming greedy selection always yields optimal window
• Using DP unnecessarily increasing complexity
• Two-pointer approach is linear, not logarithmic

2. You are given a sorted array that has been rotated at an unknown pivot. You need to find if a target value exists in the array efficiently. Which algorithmic approach guarantees an optimal O(log n) time complexity for this problem?

easy

A. Find the pivot index using binary search, then perform binary search in the appropriate subarray.

B. Apply a greedy algorithm that picks the closest element to the target at each step.

C. Use a dynamic programming approach to store intermediate results for subproblems.

D. Linear search through the entire array until the target is found.

Solution

1. Step 1: Understand problem constraints

   The array is sorted but rotated, so a simple binary search won't work directly.

2. Step 2: Identify the optimal approach

   Finding the pivot splits the array into two sorted halves, allowing binary search on the correct half, achieving O(log n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Pivot finding plus binary search is classic for rotated sorted arrays [OK]

Hint: Pivot + binary search -> O(log n) [OK]

Common Mistakes:

• Assuming linear search is efficient enough
• Confusing greedy or DP with binary search

3. What is the space complexity of the recursive binary search algorithm on an array of size n, considering the recursion call stack?

medium

A. O(log n) due to recursion call stack depth proportional to halving steps

B. O(1) constant space because no extra data structures are used

C. O(n) because each recursive call creates a new subarray copy

D. O(n log n) combining recursion depth and array size

Solution

1. Step 1: Identify recursion depth

   Binary search halves the search space each call, so max recursion depth is O(log n).

2. Step 2: Analyze space usage per call

   Each call uses constant space; no new arrays are created, so total space is O(log n) for the call stack.

3. Step 3: Clarify space complexity definition

   Since no additional data structures are created and only a fixed number of variables are used per call, the extra space excluding call stack is O(1).

4. Step 4: Distinguish between auxiliary space and call stack

   Auxiliary space is O(1), but total space including call stack is O(log n).

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   Recursive calls stack up to log n depth, no extra arrays [OK]

Hint: Recursion depth = log n -> space O(log n) [OK]

Common Mistakes:

• Assuming O(1) ignoring recursion stack
• Thinking new arrays are created each call
• Confusing time and space complexity

4. What is the time complexity of the optimal algorithm that finds the minimum element in a rotated sorted array without duplicates using modified binary search with neighbor checks?

medium

A. O(log n), because it halves the search space each iteration

B. O(log n * n), because neighbor checks add linear overhead each step

C. O(n), because in worst case it scans all elements

D. O(1), because it uses constant time comparisons

Solution

1. Step 1: Analyze loop behavior

   Each iteration halves the search space by adjusting left or right pointers based on comparisons.

2. Step 2: Neighbor checks are constant time

   Accessing prev and next indices uses modulo arithmetic, which is O(1), so no extra linear overhead.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search halves array each iteration [OK]

Hint: Binary search halves search space, neighbor checks are O(1) [OK]

Common Mistakes:

• Confusing neighbor checks as linear scan
• Assuming linear time due to rotation
• Ignoring constant time modulo operations

5. Suppose the rotated sorted array may contain duplicate elements. Which modification to the pivot-finding algorithm is necessary to correctly find the pivot in O(log n) time in the worst case?

hard

A. Add a linear scan fallback when nums[mid] == nums[high] to reduce high by one.

B. Use a hash map to store visited indices to avoid infinite loops.

C. No modification needed; the existing pivot-finding algorithm works unchanged.

D. Switch to linear search for pivot since duplicates break binary search.

Solution

1. Step 1: Understand duplicates impact

   Duplicates can cause nums[mid] == nums[high], making it unclear which half is sorted.

2. Step 2: Modify pivot search

   When nums[mid] == nums[high], reduce high by one to shrink search space safely.

3. Step 3: Complexity consideration

   This modification keeps worst-case complexity close to O(n) but often better than linear scan.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Reducing high on equality handles duplicates correctly [OK]

Hint: Handle nums[mid]==nums[high] by decrementing high [OK]

Common Mistakes:

• Assuming no duplicates
• Switching to linear search unnecessarily