# Capacity To Ship Packages Within D Days
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/capacity-to-ship-packages-within-d-days)
Canonical: https://scaleengineer.com/dsa/problems/capacity-to-ship-packages-within-d-days
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [Agoda](https://scaleengineer.com/companies/agoda), [DoorDash](https://scaleengineer.com/companies/doordash), [Expedia](https://scaleengineer.com/companies/expedia), [Flipkart](https://scaleengineer.com/companies/flipkart), [Salesforce](https://scaleengineer.com/companies/salesforce), [Zeta](https://scaleengineer.com/companies/zeta), [DP world](https://scaleengineer.com/companies/dp-world), [Mindtickle](https://scaleengineer.com/companies/mindtickle)
---
## Problem
A conveyor belt has packages that must be shipped from one port to another within `days` days.

The `ith` package on the conveyor belt has a weight of `weights[i]`. Each day, we load the ship with packages on the conveyor belt (in the order given by `weights`). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within `days` days.

**Example 1:**

**Input:** weights = [1,2,3,4,5,6,7,8,9,10], days = 5
**Output:** 15
**Explanation:** A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.

**Example 2:**

**Input:** weights = [3,2,2,4,1,4], days = 3
**Output:** 6
**Explanation:** A ship capacity of 6 is the minimum to ship all the packages in 3 days like this:
1st day: 3, 2
2nd day: 2, 4
3rd day: 1, 4

**Example 3:**

**Input:** weights = [1,2,3,1,1], days = 4
**Output:** 3
**Explanation:**
1st day: 1
2nd day: 2
3rd day: 3
4th day: 1, 1

**Constraints:**

* `1 <= days <= weights.length <= 5 * 104`
* `1 <= weights[i] <= 500`

# Approaches
## Brute Force by Linearly Searching for Capacity
This approach involves checking every possible ship capacity, one by one, starting from the minimum possible value. The minimum possible capacity must be at least the weight of the heaviest single package. We then incrementally increase the capacity and, for each value, check if it allows shipping all packages within the given number of days. The first capacity that satisfies this condition is the minimum required capacity.
**Time:** O((S - M) * N), where N is the number of packages, S is the sum of all weights, and M is the maximum weight of a single package. The outer loop runs `S - M` times, and for each iteration, we perform a simulation that takes O(N) time. This is too slow for the given constraints. · **Space:** O(1), as we only use a few variables to store the current state, regardless of the input size.
**Pros:** Simple to understand and implement.; Guaranteed to find the correct answer.
**Cons:** Extremely inefficient and will time out on larger inputs.; The number of capacities to check can be very large.
### Explanation
The core idea is to iterate through all potential capacities and test each one. The search for the capacity starts from the weight of the heaviest package (since the ship must be able to hold at least that much) and goes up to the total weight of all packages (a guaranteed upper bound). For each candidate capacity, we simulate the shipping process to determine how many days it would take. We do this by greedily loading packages for a day until the next package exceeds the current day's capacity, at which point we move to the next day. If the total days required for a given capacity is within the allowed `days`, we have found our answer, as we are checking capacities in increasing order. ```java class Solution { private boolean canShip(int[] weights, int days, int capacity) { int daysNeeded = 1; int currentWeight = 0; for (int weight : weights) { if (weight > capacity) return false; if (currentWeight + weight > capacity) { daysNeeded++; currentWeight = weight; } else { currentWeight += weight; } } return daysNeeded <= days; } public int shipWithinDays(int[] weights, int days) { int maxWeight = 0; int totalWeight = 0; for (int weight : weights) { maxWeight = Math.max(maxWeight, weight); totalWeight += weight; } for (int capacity = maxWeight; capacity <= totalWeight; capacity++) { if (canShip(weights, days, capacity)) { return capacity; } } return totalWeight; } } ```
### Algorithm
1. Calculate the lower and upper bounds for the ship's capacity. The lower bound (`min_capacity`) is the weight of the heaviest package. The upper bound (`max_capacity`) is the sum of all package weights. 2. Iterate through each possible capacity `c` from `min_capacity` to `max_capacity`. 3. For each capacity `c`, check if it's possible to ship all packages within `days`. 3a. To check, simulate the process: Initialize `days_needed = 1` and `current_load = 0`. 3b. Iterate through the `weights` array. For each `weight`, try to add it to the `current_load`. 3c. If `current_load + weight <= c`, update `current_load += weight`. 3d. If `current_load + weight > c`, a new day is required. Increment `days_needed` and set `current_load = weight`. 4. If the calculated `days_needed` is less than or equal to the given `days`, then the current capacity `c` is a valid solution. Since we are iterating from the smallest possible capacity, this is the minimum capacity. Return `c`.

## Optimal Approach using Binary Search
This problem can be solved efficiently by performing a binary search on the range of possible answers for the ship's capacity. The key insight is that the feasibility of shipping packages within a certain number of days is a monotonic function of the ship's capacity. If a ship with capacity `C` can do the job, any ship with a capacity greater than `C` can also do it. This property allows us to use binary search to quickly find the minimum required capacity.
**Time:** O(N * log(S)), where N is the number of packages and S is the sum of all weights. The binary search performs `log(S)` iterations (more precisely, `log(S - M)` where M is the max weight), and in each iteration, we call the `isFeasible` function which takes O(N) time to iterate through all packages. · **Space:** O(1), as the algorithm uses a constant amount of extra space for variables, regardless of the input size.
**Pros:** Highly efficient, utilizing the monotonic nature of the problem.; Guaranteed to find the optimal solution quickly, well within time limits for large inputs.
**Cons:** Slightly more complex to conceptualize than the brute-force approach, as it requires understanding binary search on an answer space.
### Explanation
We first establish a search space for the capacity. The minimum possible capacity is the weight of the heaviest package (`max(weights)`), and a safe maximum is the sum of all weights (`sum(weights)`). We then apply binary search within this range `[max(weights), sum(weights)]`. In each step of the binary search, we pick a candidate capacity `mid`. We then check if it's feasible to ship all packages within `days` with this capacity. This feasibility check is done by a helper function that greedily simulates the loading process in O(N) time. If the `mid` capacity is feasible (i.e., requires `days` or fewer), it means we might be able to do even better with a smaller capacity. So, we record `mid` as a potential answer and try searching in the lower half of the range: `high = mid - 1`. If the `mid` capacity is not feasible, it's too small. We must increase the capacity, so we search in the upper half: `low = mid + 1`. This process continues until the search space is exhausted (`low > high`), at which point we will have found the smallest capacity that works. ```java class Solution { private boolean isFeasible(int[] weights, int days, int capacity) { int daysNeeded = 1; int currentWeight = 0; for (int weight : weights) { if (currentWeight + weight > capacity) { daysNeeded++; currentWeight = weight; } else { currentWeight += weight; } } return daysNeeded <= days; } public int shipWithinDays(int[] weights, int days) { int low = 0; int high = 0; for (int weight : weights) { low = Math.max(low, weight); high += weight; } int minCapacity = high; while (low <= high) { int mid = low + (high - low) / 2; if (isFeasible(weights, days, mid)) { minCapacity = mid; high = mid - 1; } else { low = mid + 1; } } return minCapacity; } } ```
### Algorithm
1. Define the search range for the capacity. The lower bound `low` is the maximum individual package weight. The upper bound `high` is the total weight of all packages. 2. Initialize a variable `ans` to store the minimum feasible capacity, initially set to `high`. 3. While `low <= high`: 3a. Calculate the middle capacity: `mid = low + (high - low) / 2`. 3b. Check if this `mid` capacity is feasible using a helper function. The helper function simulates the shipping process greedily and returns `true` if the number of days required is at most `days`. 3c. If `mid` is a feasible capacity: this could be our answer, but we want the minimum. So, we store it (`ans = mid`) and try to find a smaller capacity by setting `high = mid - 1`. 3d. If `mid` is not a feasible capacity: it's too small. We need a larger capacity, so we set `low = mid + 1`. 4. After the loop terminates, `ans` (or `low` depending on implementation) will hold the minimum capacity required.

# Solutions
### Java

```java
class Solution { public int shipWithinDays ( int [] weights , int days ) { int left = 0 , right = 0 ; for ( int w : weights ) { left = Math . max ( left , w ); right += w ; } while ( left < right ) { int mid = ( left + right ) >> 1 ; if ( check ( mid , weights , days )) { right = mid ; } else { left = mid + 1 ; } } return left ; } private boolean check ( int mx , int [] weights , int days ) { int ws = 0 , cnt = 1 ; for ( int w : weights ) { ws += w ; if ( ws > mx ) { ws = w ; ++ cnt ; } } return cnt <= days ; } }
```

### CPP

```cpp
class Solution { public: int shipWithinDays ( vector < int >& weights , int days ) { int left = 0 , right = 0 ; for ( auto & w : weights ) { left = max ( left , w ); right += w ; } auto check = [ & ]( int mx ) { int ws = 0 , cnt = 1 ; for ( auto & w : weights ) { ws += w ; if ( ws > mx ) { ws = w ; ++ cnt ; } } return cnt <= days ; }; while ( left < right ) { int mid = ( left + right ) >> 1 ; if ( check ( mid )) { right = mid ; } else { left = mid + 1 ; } } return left ; } };
```

### Python

```python
class Solution : def shipWithinDays ( self , weights : List [ int ], days : int ) -> int : def check ( mx ): ws , cnt = 0 , 1 for w in weights : ws += w if ws > mx : cnt += 1 ws = w return cnt <= days left , right = max ( weights ), sum ( weights ) + 1 return left + bisect_left ( range ( left , right ), True , key = check )
```