Skip to main content
Talentd

Capacity To Ship Packages Within D Days - Solution & Explanation

MediumArrayBinary Search17 min readAsked at: Amazon, Microsoft, Apple +17
Practice this problem

Problem Statement

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

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.

In this C solution, we define a helper function canShip which checks if a given capacity can ship all packages within the specified days. We use binary search in the shipWithinDays function to find the minimal capacity required, by adjusting the search bounds based on the feasibility determined by canShip.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log m), where n is the number of packages and m is the range of the binary search (sum of weights - max weight).
Space Complexity: O(1), as we use constant extra space.

Try this approach in the editor →

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.

This C solution incrementally increases the capacity from the maximum package weight. With each increment, we check if the current capacity is sufficient to ship within the given days using canShip. This approach may take longer due to its linear simulation nature.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * C/m), where C/m is the number of increments in the worst case.
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Binary Search

Time Complexity: O(n log m), where n is the number of packages and m is the range of the binary search (sum of weights - max weight).
Space Complexity: O(1), as we use constant extra space.

Approach 2: Greedy Simulation

Time Complexity: O(n * C/m), where C/m is the number of increments in the worst case.
Space Complexity: O(1).

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 CheckO(n log S)O(1)Optimal solution for large inputs; exploits monotonic capacity feasibility

Video Solution

BS-15. Capacity to Ship Packages within D Days • take U forward • 267,431 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Capacity To Ship Packages Within D Days with our built-in code editor and test cases.

Practice on FleetCode
Previous

Cutting Ribbons

Next

Divide Chocolate