Capacity to Ship Packages

▶

Steps

setup

Initialize Search Space

Set left to the maximum single package weight (10) and right to the sum of all weights (55). This defines the initial search space for ship capacity.

💡 The minimum capacity must be at least the heaviest package, and at most the sum of all packages if shipped in one day.

Line:

left, right = max(weights), sum(weights)

💡 Establishes the bounds for binary searching the minimum feasible capacity.

compare

Calculate Mid Capacity

Calculate mid as (10 + 55) // 2 = 32. This is the candidate capacity to test feasibility.

💡 Mid splits the search space to test if capacity 32 can ship all packages in 5 days.

Line:

mid = (left + right) // 2

💡 Mid is the current guess for minimum capacity.

compare

Check Feasibility for Capacity 32

Simulate shipping packages with capacity 32. Group packages until capacity exceeded, counting days used.

💡 This step tests if capacity 32 can ship all packages within 5 days.

Line:

if can_ship_early_stop(weights, days, mid):

💡 Feasibility check determines if capacity is sufficient or needs to increase.

shrink

Update Right Bound to Mid

Since capacity 32 is feasible, reduce right to 32 to search for smaller feasible capacities.

💡 We try to find a smaller capacity that still works, so we shrink the upper bound.

Line:

right = mid

💡 Shrinking the search space from the right narrows down the minimum capacity.

compare

Calculate New Mid Capacity

Calculate mid as (10 + 32) // 2 = 21 to test a smaller capacity.

💡 Mid recalculates to test if capacity 21 can still ship in 5 days.

Line:

mid = (left + right) // 2

💡 Mid moves closer to the lower bound to find minimal feasible capacity.

compare

Check Feasibility for Capacity 21

Simulate shipping with capacity 21; check if all packages ship within 5 days.

💡 This tests if capacity 21 is sufficient or too small.

Line:

if can_ship_early_stop(weights, days, mid):

💡 Feasibility check guides whether to increase or decrease capacity.

shrink

Update Right Bound to Mid

Capacity 21 is feasible, so update right to 21 to try smaller capacities.

💡 We continue shrinking the upper bound to find the minimal capacity.

Line:

right = mid

💡 Search space shrinks from the right again.

compare

Calculate New Mid Capacity

Calculate mid as (10 + 21) // 2 = 15 to test an even smaller capacity.

💡 Mid moves closer to the lower bound to test minimal capacity.

Line:

mid = (left + right) // 2

💡 Mid tests a smaller candidate capacity.

compare

Check Feasibility for Capacity 15

Simulate shipping with capacity 15; check if all packages ship within 5 days.

💡 This tests if capacity 15 is sufficient or too small.

Line:

if can_ship_early_stop(weights, days, mid):

💡 Feasibility check confirms if 15 is minimal feasible capacity.

shrink

Update Right Bound to Mid

Capacity 15 is feasible, so update right to 15 to try even smaller capacities.

💡 We try to find if any capacity smaller than 15 can still work.

Line:

right = mid

💡 Search space shrinks further from the right.

compare

Calculate New Mid Capacity

Calculate mid as (10 + 15) // 2 = 12 to test smaller capacity.

💡 Mid moves closer to lower bound to test if 12 is feasible.

Line:

mid = (left + right) // 2

💡 Mid tests a smaller candidate capacity.

compare

Check Feasibility for Capacity 12

Simulate shipping with capacity 12; check if all packages ship within 5 days.

💡 This tests if capacity 12 is sufficient or too small.

Line:

if can_ship_early_stop(weights, days, mid):

💡 Feasibility check guides next search space update.

expand

Update Left Bound to Mid + 1

Capacity 12 is not feasible, so increase left to 13 to try larger capacities.

💡 We discard capacities ≤ 12 because they cannot ship in 5 days.

Line:

left = mid + 1

💡 Search space shrinks from the left to exclude insufficient capacities.

compare

Calculate New Mid Capacity

Calculate mid as (13 + 15) // 2 = 14 to test capacity 14.

💡 Mid tests capacity 14 to check feasibility.

Line:

mid = (left + right) // 2

💡 Mid moves within the narrowed search space.

compare

Check Feasibility for Capacity 14

Simulate shipping with capacity 14; check if all packages ship within 5 days.

💡 This tests if capacity 14 is sufficient or too small.

Line:

if can_ship_early_stop(weights, days, mid):

💡 Feasibility check guides final search space update.

expand

Update Left Bound to Mid + 1

Capacity 14 is not feasible, so increase left to 15.

💡 Discard capacities ≤ 14 as insufficient.

Line:

left = mid + 1

💡 Search space narrows to a single candidate capacity.

prune

Termination: Left Meets Right

Left equals right at 15, so the minimum feasible capacity is found.

💡 When lo meets hi, the binary search concludes with the answer.

Line:

return left

💡 The smallest capacity to ship all packages in 5 days is 15.

def can_ship_early_stop(weights, days, capacity):
    day_count = 1  # STEP 3,6,9,12,15
    current_load = 0
    for w in weights:
        if current_load + w > capacity:
            day_count += 1
            if day_count > days:
                return False
            current_load = 0
        current_load += w
    return True

def ship_with_capacity_binary_search_early_stop(weights, days):
    left, right = max(weights), sum(weights)  # STEP 1
    while left < right:
        mid = (left + right) // 2  # STEP 2,5,8,11,14
        if can_ship_early_stop(weights, days, mid):  # STEP 3,6,9,12,15
            right = mid  # STEP 4,7,10,13,16
        else:
            left = mid + 1
    return left  # STEP 17

if __name__ == '__main__':
    weights = [1,2,3,4,5,6,7,8,9,10]
    days = 5
    print(ship_with_capacity_binary_search_early_stop(weights, days))

📊

Capacity to Ship Packages - Watch the Algorithm Execute, Step by Step

Watching each step shows how the search space shrinks and why certain capacities are feasible or not, making the binary search on answer space intuitive.

1

0

2

1

3

2

4

3

5

4

6

5

7

6

8

7

9

8

10

9

Next: lo=10 hi=55

Target: 32

1

0

2

1

3

2

4

3

5

4

6

5

7

6

8

7

9

8

10

9

Next: lo=10 hi=55

Target: 32

1

0

2

1

3

2

4

3

5

4

6

5

7

6

8

7

9

8

10

9

Next: lo=10 hi=32

Target: 32

1

0

2

1

3

2

4

3

5

4

6

5

7

6

8

7

9

8

10

9

Next: lo=10 hi=32

Target: 21

1

0

2

1

3

2

4

3

5

4

6

5

7

6

8

7

9

8

10

9

Next: lo=10 hi=32

Target: 21

1

0

2

1

3

2

4

3

5

4

6

5

7

6

8

7

9

8

10

9

Next: lo=10 hi=21

Target: 21

1

0

2

1

3

2

4

3

5

4

6

5

7

6

8

7

9

8

10

9

Next: lo=10 hi=21

Target: 15

1

0

2

1

3

2

4

3

5

4

6

5

7

6

8

7

9

8

10

9

Next: lo=10 hi=21

Target: 15

1

0

2

1

3

2

4

3

5

4

6

5

7

6

8

7

9

8

10

9

Next: lo=10 hi=15

Target: 15

1

0

2

1

3

2

4

3

5

4

6

5

7

6

8

7

9

8

10

9

Next: lo=10 hi=15

Target: 12

1

0

2

1

3

2

4

3

5

4

6

5

7

6

8

7

9

8

10

9

Next: lo=10 hi=15

Target: 12

1

0

2

1

3

2

4

3

5

4

6

5

7

6

8

7

9

8

10

9

Next: lo=13 hi=15

Target: 12

1

0

2

1

3

2

4

3

5

4

6

5

7

6

8

7

9

8

10

9

Next: lo=13 hi=15

Target: 14

1

0

2

1

3

2

4

3

5

4

6

5

7

6

8

7

9

8

10

9

Next: lo=13 hi=15

Target: 14

1

0

2

1

3

2

4

3

5

4

6

5

7

6

8

7

9

8

10

9

Next: lo=15 hi=15

Target: 14

1

0

2

1

3

2

4

3

5

4

6

5

7

6

8

7

9

8

10

9

Next: lo=15 hi=15

1

0

2

1

3

2

4

3

5

4

6

5

7

6

8

7

9

8

10

9

Next: lo=15 hi=15

Key Takeaways

✓ Binary search on answer space efficiently finds the minimal feasible capacity without enumerating all capacities.

This insight is hard to see from code alone because the search space is not array indices but capacity values.

✓ Feasibility checks with early stopping prevent unnecessary computation by stopping once days exceed the limit.

Watching the simulation of grouping packages clarifies how capacity affects day count.

✓ Adjusting left and right bounds based on feasibility results shows how the search space shrinks to the exact answer.

Seeing each update step-by-step reveals the logic behind binary search convergence.

Practice

1. Consider the following Python code implementing the min-heap approach to find the kth smallest element in a sorted matrix. Given the matrix [[1,3],[2,4]] and k = 3, what value does the function return?

easy

A. 2

B. 4

C. 3

D. 1

Solution

1. Step 1: Initialize min-heap with first elements

   Push (1,0,0) and (2,1,0) into heap.

2. Step 2: Extract elements until count == k

   Pop 1 (count=1), push 3 from row 0; pop 2 (count=2), push 4 from row 1; pop 3 (count=3), return 3.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Third smallest element is 3 [OK]

Hint: Trace heap pops and pushes carefully [OK]

Common Mistakes:

• Off-by-one counting of popped elements
• Returning wrong popped value
• Confusing row and column indices

2. Consider the following code snippet implementing the optimal binary search to find the single element in a sorted array where every other element appears twice. What is the returned value when the input is [1,1,2,3,3]?

easy

A. 3

B. 1

C. 2

D. Error due to index out of range

Solution

1. Step 1: Trace first iteration with low=0, high=4

   mid = 2 (even), nums[2]=2, nums[3]=3 not equal, so high = mid = 2

2. Step 2: Trace second iteration with low=0, high=2

   mid = 1 (odd), nums[1]=1, nums[0]=1 equal, so low = mid + 1 = 2

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Loop ends with low=2, nums[2]=2 returned [OK]

Hint: Check parity and compare adjacent elements carefully [OK]

Common Mistakes:

• Off-by-one errors in mid calculation
• Confusing even/odd parity logic
• Assuming index out of range error

3. The following code attempts to find the kth positive missing number from a sorted array arr. Which line contains a subtle bug that causes incorrect results for some inputs?

def findKthPositive(arr, k):
    n = len(arr)
    total_missing = arr[-1] - n
    if k > total_missing:
        return arr[-1] + (k - total_missing)
    left, right = 0, n - 1
    while left <= right:
        mid = (left + right) // 2
        missing = arr[mid] - mid  # Bug here
        if missing < k:
            left = mid + 1
        else:
            right = mid - 1
    return arr[right] + (k - (arr[right] - (right + 1)))

medium

A. Line returning arr[right] + (k - (arr[right] - (right + 1)))

B. Line calculating total_missing = arr[-1] - n

C. Line updating left = mid + 1

D. Line calculating missing = arr[mid] - mid

Solution

1. Step 1: Identify the missing count formula

   The correct missing count at index mid is arr[mid] - (mid + 1), since indices are zero-based but numbers start at 1.

2. Step 2: Analyze the bug impact

   Using arr[mid] - mid undercounts missing numbers by 1, causing incorrect binary search decisions and wrong final result.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct missing count formula is arr[mid] - (mid + 1) [OK]

Hint: Missing count must subtract (mid + 1), not mid [OK]

Common Mistakes:

• Off-by-one in missing count calculation
• Incorrect binary search boundary updates
• Ignoring missing numbers before first element

4. What is the time complexity of the optimal binary search solution for finding the minimum speed to arrive on time, given n distances and a precision epsilon for floating point speed search?

medium

A. O(log n * (maxSpeed / epsilon))

B. O(n * maxSpeed)

C. O(n^2 * log(maxSpeed))

D. O(n * log((maxSpeed - minSpeed) / epsilon))

Solution

1. Step 1: Identify the binary search iterations

   Binary search on speed range [minSpeed, maxSpeed] with precision epsilon takes O(log((maxSpeed - minSpeed)/epsilon)) steps.

2. Step 2: Calculate per-iteration cost

   Each feasibility check sums over n distances, so O(n) per iteration.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Combining steps yields O(n log((maxSpeed - minSpeed)/epsilon)) [OK]

Hint: Binary search iterations times linear feasibility check [OK]

Common Mistakes:

• Confusing maxSpeed with n
• Ignoring epsilon precision in log factor

5. Suppose the problem is modified so that the array can contain multiple identical adjacent elements (plateaus), and you want to find any peak element efficiently. Which modification to the original modified binary search algorithm correctly handles this scenario without degrading to linear time?

hard

A. Change the comparison to nums[mid] <= nums[mid + 1] and recurse right if true, else left

B. Skip over equal adjacent elements by moving mid until nums[mid] != nums[mid + 1] before comparison

C. Use linear scan since binary search cannot handle plateaus correctly

D. Modify recursion to always recurse left half to find the first peak

Solution

1. Step 1: Understand plateau challenge

   Equal adjacent elements break strict inequality assumptions in original binary search.

2. Step 2: Modify comparison to handle equality

   Using ≤ ensures recursion moves right when plateau or increasing slope, preserving O(log n) time.

3. Step 3: Avoid linear scan or skipping elements

   Skipping elements or linear scan can degrade performance; always recursing left loses efficiency.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Modified comparison handles plateaus without extra overhead [OK]

Hint: Use <= comparison to handle plateaus in binary search [OK]

Common Mistakes:

• Trying to skip equal elements linearly
• Assuming linear scan is necessary
• Always recursing one side losing log n guarantee