Capacity To Ship Packages Within D Days - Solution & Explanation

Problem Overview: You are given an array weights where each element represents the weight of a package on a conveyor belt. Packages must be shipped in order. The task is to find the minimum ship capacity required so all packages are delivered within D days.

Approach 1: Binary Search on Capacity (O(n log S) time, O(1) space)

The key observation: if a ship capacity C can deliver all packages within D days, then any capacity greater than C will also work. This monotonic property allows you to apply binary search on the answer. The lower bound is the maximum weight in the array (a ship must carry the heaviest package), and the upper bound is the sum of all weights (ship everything in one day). For each candidate capacity, simulate the shipping process: iterate through the array and accumulate weights until exceeding the capacity, then increment the day counter and start a new load. If the number of days needed is ≤ D, reduce the search range; otherwise increase the capacity.

This approach combines binary search with a linear feasibility check over the array. Each check runs in O(n), and binary search runs over the capacity range up to the total weight, giving overall complexity O(n log S), where S is the sum of all weights.

Approach 2: Greedy Simulation (O(n * S) time, O(1) space)

A straightforward approach tries capacities sequentially starting from the maximum package weight. For each capacity, simulate the shipping process using a greedy rule: keep adding packages to the current day's load until the next package would exceed the capacity, then move to the next day. If all packages are delivered within D days, that capacity works. Otherwise increase the capacity and repeat.

This method uses the same greedy loading logic but without the search optimization. In the worst case you may test many capacities between the maximum weight and total weight, which leads to O(n * S) time complexity. The idea is simple and useful for understanding the feasibility check that powers the optimized solution.

Recommended for interviews: The expected solution is the binary search approach. Interviewers look for recognition of the monotonic search space and the ability to combine binary search with a greedy feasibility check. Showing the greedy simulation first demonstrates understanding of the shipping constraint, while the binary search optimization shows strong problem-solving and algorithmic thinking.