#1011
Capacity To Ship Packages Within D Days
MediumArrayBinary SearchBinary SearchGreedy Algorithms
Approaches
Brute ForceOptimal
Complexity Comparison
| Brute Force | Optimal Solution★ | |
|---|---|---|
| Time | O(n²) | O(n log m) |
| Space | O(1) | O(1) |
💡
Intuition
Time O(n log m)Space O(1)
The optimal solution uses binary search to efficiently find the minimum ship capacity. It narrows down the possible capacities by checking if a certain capacity can ship all packages within the given days.
⚙️
Algorithm
3 steps- 1Step 1: Set the lower bound as the maximum weight of a single package and the upper bound as the total weight of all packages.
- 2Step 2: Perform binary search: calculate the mid-point capacity and check if it can ship within the given days using the helper function.
- 3Step 3: If it can ship, update the upper bound; if not, update the lower bound. Repeat until bounds converge.
solution.py29 lines
1# Full working Python code
2
3def canShip(weights, capacity, days):
4 total_days = 1
5 current_weight = 0
6 for weight in weights:
7 current_weight += weight
8 if current_weight > capacity:
9 total_days += 1
10 current_weight = weight
11 if total_days > days:
12 return False
13 return True
14
15def shipWithinDays(weights, days):
16 left = max(weights)
17 right = sum(weights)
18 while left < right:
19 mid = (left + right) // 2
20 if canShip(weights, mid, days):
21 right = mid
22 else:
23 left = mid + 1
24 return left
25
26# Example usage
27weights = [1,2,3,4,5,6,7,8,9,10]
28days = 5
29print(shipWithinDays(weights, days))ℹ
Complexity note: The complexity is O(n log m) where n is the number of packages and m is the range of possible capacities (from max weight to total weight). The binary search reduces the number of checks significantly.
- 1Binary search is a powerful technique for optimizing search problems, especially when the search space is continuous.
- 2Understanding how to simulate the loading process is crucial to determining if a given capacity is feasible.
Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.