Binary Search on Answer Explained: Capacity to Ship Packages Within D Days (Python)

Capacity To Ship Packages Within D Days – Binary Search on Answer

This problem is a classic example of the Binary Search on Answer pattern. Instead of searching within the array, we search over the range of possible ship capacities and determine the minimum capacity required to ship all packages within the given number of days.

Problem Intuition

We are given a list of package weights that must be shipped in the same order within a fixed number of days. Each day, the ship has a fixed capacity and we load packages sequentially until the capacity is exceeded, after which shipping continues the next day.

The key observation is that:

• If a certain ship capacity works, then any larger capacity will also work.
• If a capacity does not work, then any smaller capacity will also fail.

This monotonic behavior allows us to apply binary search efficiently.

Search Space

We define our binary search range carefully:

• Minimum capacity is the maximum weight in the array, since the ship must be able to carry the heaviest package.
• Maximum capacity is the sum of all weights, which represents shipping everything in a single day.

Feasibility Check

For a guessed capacity, we simulate the shipping process day by day. We keep adding package weights until the capacity is exceeded. When that happens, we move to the next day and continue.

If we can finish shipping all packages without running out of days, the capacity is considered valid.

Algorithm Explanation

1. Initialize binary search boundaries using minimum and maximum possible capacities.
2. Pick a middle capacity.
3. Check if shipping is possible with this capacity.
4. If possible, try to find a smaller valid capacity.
5. If not possible, increase the capacity.
6. Repeat until the minimum valid capacity is found.

Time and Space Complexity

The feasibility check runs in linear time, and binary search runs in logarithmic time over the capacity range.

• Time Complexity: O(n log(sum(weights)))
• Space Complexity: O(1)

Why This Approach Is Important

The Binary Search on Answer pattern appears in many interview problems. Mastering this technique makes it much easier to solve problems involving optimization under constraints.

This same approach can be applied to problems like splitting arrays, scheduling workloads, and minimizing maximum values under constraints.

Source Code

The complete implementation is available on GitHub:

View Solution on GitHub