Capacity To Ship Packages Within D Days solution and explanation
Google
9 more videos on this problem
BS-15. Capacity to Ship Packages within D Daystake U forward · 20:36 · 267K views
Capacity to Ship Packages - Leetcode 1011 - PythonNeetCodeIO · 12:25 · 40K views
Capacity To Ship Packages Within D Days Leetcode 1011 Solution Binary Search Gfg Problem of the dayCode with Alisha · 15:37 · 9K views
Leetcode 1011 Capacity To Ship Packages Within D Days JAVA How to figure it requires Binary Search?Bharat Singh · 15:00 · 9K views
Capacity to Ship Packages Within D Days (LeetCode 1011) | Full Solution with visuals and animationsNikhil Lohia · 18:07 · 9K views
LeetCode 1011. Capacity To Ship Packages Within D DaysHappy Coding · 12:42 · 5K views
Leetcode 1011 | Capacity To Ship Packages Within D Days | Binary Search | Divide and ConquerHellgeek Arena · 13:32 · 2K views
1011. Capacity To Ship Packages Within D Days | LeetCode Problem of Day | LeetCode POTDDeep Tech · 15:49 · 1K views
LeetCode 1011 Capacity To Ship Packages Within D DaysJeevan Kumar - Cracckify · 9:42 · 1K views
Capacity to Ship Packages within D Days | Leetcode 1011 Solution | Binary SearchJeevan Kumar - Cracckify · 7:36 · 686 views
The 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 * 1041 <= weights[i] <= 500
Approach overview
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.
Approach 1: Approach 1: Binary Search
This approach utilizes a binary search to find the minimal ship capacity that can carry all packages within the specified number of days. The binary search operates over the range from the maximum value in the weights array to the sum of all weights, which are the logical lower and upper bounds for the ship capacity.
class Solution:
def canShip(self, weights, days, capacity):
total, day_count = 0, 1
for weight in weights:
if total + weight > capacity:
day_count += 1
total = 0
total += weight
return day_count <= days
def shipWithinDays(self, weights, days):
left, right = max(weights), sum(weights)
while left < right:
mid = left + (right - left) // 2
if self.canShip(weights, days, mid):
right = mid
else:
left = mid + 1
return left
# Example usage
solution = Solution()
weights = [1,2,3,4,5,6,7,8,9,10]
days = 5
print(solution.shipWithinDays(weights,days)) # Output: 15import java.util.*;
class Solution {
public boolean canShip(int[] weights, int days, int capacity) {
int total = 0, dayCount = 1;
for (int weight : weights) {
if (total + weight > capacity) {
dayCount++;
total = 0;
}
total += weight;
}
return dayCount <= days;
}
public int shipWithinDays(int[] weights, int days) {
int left = Arrays.stream(weights).max().getAsInt();
int right = Arrays.stream(weights).sum();
while (left < right) {
int mid = left + (right - left) / 2;
if (canShip(weights, days, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] weights = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int days = 5;
System.out.println(sol.shipWithinDays(weights, days)); // Output: 15
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool canShip(const vector<int>& weights, int days, int capacity) {
int total = 0, dayCount = 1;
for (int weight : weights) {
if (total + weight > capacity) {
dayCount++;
total = 0;
}
total += weight;
}
return dayCount <= days;
}
int shipWithinDays(vector<int>& weights, int days) {
int left = *max_element(weights.begin(), weights.end());
int right = accumulate(weights.begin(), weights.end(), 0);
while (left < right) {
int mid = left + (right - left) / 2;
if (canShip(weights, days, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
int main() {
vector<int> weights = {1,2,3,4,5,6,7,8,9,10};
int days = 5;
cout << shipWithinDays(weights, days) << endl; // Output: 15
return 0;
}function canShip(weights, days, capacity) {
let total = 0, dayCount = 1;
for (let weight of weights) {
if (total + weight > capacity) {
dayCount++;
total = 0;
}
total += weight;
}
return dayCount <= days;
}
function shipWithinDays(weights, days) {
let left = Math.max(...weights);
let right = weights.reduce((acc, val) => acc + val, 0);
while (left < right) {
let mid = Math.floor(left + (right - left) / 2);
if (canShip(weights, days, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
const weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5;
console.log(shipWithinDays(weights, days)); // Output: 15#include <stdio.h>
int canShip(int weights[], int size, int days, int capacity) {
int total = 0, dayCount = 1;
for (int i = 0; i < size; i++) {
if (total + weights[i] > capacity) {
dayCount++;
total = 0;
}
total += weights[i];
}
return dayCount <= days;
}
int shipWithinDays(int* weights, int size, int days) {
int left = weights[0], right = 0;
for (int i = 0; i < size; i++) {
if (weights[i] > left) { left = weights[i]; }
right += weights[i];
}
while (left < right) {
int mid = left + (right - left) / 2;
if (canShip(weights, size, days, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
int main() {
int weights[] = {1,2,3,4,5,6,7,8,9,10};
int days = 5;
int size = sizeof(weights)/sizeof(weights[0]);
printf("%d\n", shipWithinDays(weights, size, days)); // Output: 15
return 0;
}using System;
using System.Linq;
class Solution {
public bool CanShip(int[] weights, int days, int capacity) {
int total = 0, dayCount = 1;
foreach (int weight in weights) {
if (total + weight > capacity) {
dayCount++;
total = 0;
}
total += weight;
}
return dayCount <= days;
}
public int ShipWithinDays(int[] weights, int days) {
int left = weights.Max();
int right = weights.Sum();
while (left < right) {
int mid = left + (right - left) / 2;
if (CanShip(weights, days, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
static void Main() {
Solution solution = new Solution();
int[] weights = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int days = 5;
Console.WriteLine(solution.ShipWithinDays(weights, days)); // Output: 15
}
}The Python solution defines a canShip method to determine the feasibility of shipping with a given capacity. The main shipWithinDays function applies binary search to find the minimum capacity required. The process iterates until the ideal capacity is found.
Time Complexity: O(n log m) with n as the number of weights elements and m indicating the search range.
Space Complexity: O(1) since no extra data structures are used.
Approach 2: Approach 2: Greedy Simulation
This approach involves greedy simulation to estimate the minimum capacity by incrementing from the largest single package weight until you find a capacity that can ship all the packages within the days. Note that this approach may take more time in the worst case due to the linear increment.
class Solution:
def canShip(self, weights, days, capacity):
total, day_count = 0, 1
for weight in weights:
if total + weight > capacity:
day_count += 1
total = 0
total += weight
return day_count <= days
def shipWithinDays(self, weights, days):
left = max(weights)
while not self.canShip(weights, days, left):
left += 1
return left
# Example usage
solution = Solution()
weights = [1,2,3,4,5,6,7,8,9,10]
days = 5
print(solution.shipWithinDays(weights, days)) # Output: 15import java.util.*;
class Solution {
public boolean canShip(int[] weights, int days, int capacity) {
int total = 0, dayCount = 1;
for (int weight : weights) {
if (total + weight > capacity) {
dayCount++;
total = 0;
}
total += weight;
}
return dayCount <= days;
}
public int shipWithinDays(int[] weights, int days) {
int left = Arrays.stream(weights).max().getAsInt();
while (!canShip(weights, days, left)) {
left++;
}
return left;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] weights = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int days = 5;
System.out.println(sol.shipWithinDays(weights, days)); // Output: 15
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool canShip(const vector<int>& weights, int days, int capacity) {
int total = 0, dayCount = 1;
for (int weight : weights) {
if (total + weight > capacity) {
dayCount++;
total = 0;
}
total += weight;
}
return dayCount <= days;
}
int shipWithinDays(vector<int>& weights, int days) {
int left = *max_element(weights.begin(), weights.end());
while (!canShip(weights, days, left))
left++;
return left;
}
int main() {
vector<int> weights = {1,2,3,4,5,6,7,8,9,10};
int days = 5;
cout << shipWithinDays(weights, days) << endl; // Output: 15
return 0;
}function canShip(weights, days, capacity) {
let total = 0, dayCount = 1;
for (let weight of weights) {
if (total + weight > capacity) {
dayCount++;
total = 0;
}
total += weight;
}
return dayCount <= days;
}
function shipWithinDays(weights, days) {
let left = Math.max(...weights);
while (!canShip(weights, days, left)) {
left++;
}
return left;
}
const weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5;
console.log(shipWithinDays(weights, days)); // Output: 15#include <stdio.h>
int canShip(int weights[], int size, int days, int capacity) {
int total = 0, dayCount = 1;
for (int i = 0; i < size; i++) {
if (total + weights[i] > capacity) {
dayCount++;
total = 0;
}
total += weights[i];
}
return dayCount <= days;
}
int shipWithinDays(int* weights, int size, int days) {
int left = weights[0];
for (int i = 0; i < size; i++) {
if (weights[i] > left) { left = weights[i]; }
}
while (!canShip(weights, size, days, left)) {
left++;
}
return left;
}
int main() {
int weights[] = {1,2,3,4,5,6,7,8,9,10};
int days = 5;
int size = sizeof(weights)/sizeof(weights[0]);
printf("%d\n", shipWithinDays(weights, size, days)); // Output: 15
return 0;
}using System;
using System.Linq;
class Solution {
public bool CanShip(int[] weights, int days, int capacity) {
int total = 0, dayCount = 1;
foreach (int weight in weights) {
if (total + weight > capacity) {
dayCount++;
total = 0;
}
total += weight;
}
return dayCount <= days;
}
public int ShipWithinDays(int[] weights, int days) {
int left = weights.Max();
while (!CanShip(weights, days, left))
left++;
return left;
}
static void Main() {
Solution solution = new Solution();
int[] weights = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int days = 5;
Console.WriteLine(solution.ShipWithinDays(weights, days)); // Output: 15
}
}The Python solution uses a loop to incrementally increase the shipping capacity from the maximum weight until a feasible capacity is found that meets the constraint. The method canShip evaluates each capacity.
Time Complexity: O(n * C/m).
Space Complexity: O(1).
Approach 3: Default Approach
function shipWithinDays(weights: number[], days: number): number {
let left = 0;
let right = 0;
for (const w of weights) {
left = Math.max(left, w);
right += w;
}
const check = (mx: number) => {
let ws = 0;
let cnt = 1;
for (const w of weights) {
ws += w;
if (ws > mx) {
ws = w;
++cnt;
}
}
return cnt <= days;
};
while (left < right) {
const mid = (left + right) >> 1;
if (check(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}func shipWithinDays(weights []int, days int) int {
var left, right int
for _, w := range weights {
if left < w {
left = w
}
right += w
}
return left + sort.Search(right, func(mx int) bool {
mx += left
ws, cnt := 0, 1
for _, w := range weights {
ws += w
if ws > mx {
ws = w
cnt++
}
}
return cnt <= days
})
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Binary Search | Time Complexity: O(n log m) with n as the number of weights elements and m indicating the search range. |
| Approach 2: Greedy Simulation | Time Complexity: O(n * C/m). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Simulation (Sequential Capacity Check) | O(n * S) | O(1) | When building intuition for the feasibility check or when constraints are very small |
| Binary Search on Capacity + Greedy Check | O(n log S) | O(1) | Optimal solution for large inputs; exploits monotonic capacity feasibility |
Frequently asked questions
Is Capacity To Ship Packages Within D Days easy or hard?
Capacity To Ship Packages Within D Days is rated Medium on LeetCode. The greedy simulation itself is straightforward, but recognizing that the answer can be found using binary search over the capacity range is the main challenge.
Capacity To Ship Packages Within D Days Python/Java solution
Most implementations follow the same structure: binary search over capacity and a helper function that simulates shipping. The helper iterates through the weights array and counts how many days are needed for a given capacity. This pattern translates cleanly to Python, Java, C++, JavaScript, and other languages.
How to solve Capacity To Ship Packages Within D Days in O(n log S)?
Use binary search over the possible ship capacities. The lower bound is the maximum element in the weights array, and the upper bound is the total sum of weights. For each mid capacity, iterate through the array and greedily load packages until the capacity is exceeded, counting the number of days needed. Adjust the search range based on whether the result fits within D days.
What is the best approach for Capacity To Ship Packages Within D Days?
The best approach uses binary search on the ship capacity combined with a greedy feasibility check. The search range is between the maximum package weight and the total weight of all packages. For each capacity guess, simulate loading packages in order and count how many days are required. This solution runs in O(n log S) time and O(1) space.
Is Capacity To Ship Packages Within D Days asked at Google/Amazon/Meta?
Capacity To Ship Packages Within D Days is a common binary search interview problem and appears frequently in Amazon-style interview preparation lists. Variants of the same pattern (binary search on answer with feasibility checks) are asked across companies including Google, Meta, and Microsoft.
What data structure is used in Capacity To Ship Packages Within D Days?
The problem mainly uses an array traversal combined with binary search on the answer space. No advanced data structures are required. The feasibility check relies on greedy accumulation of weights while iterating through the array.
What is the time complexity of Capacity To Ship Packages Within D Days?
The optimal solution runs in O(n log S) time, where n is the number of packages and S is the sum of all package weights (the capacity search range). Each binary search step performs a linear scan of the array to simulate shipping. Space complexity is O(1) because only a few counters are used.