Coding

Capacity to Ship Packages Within D Days

Asked at

Flexport

Meta

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

You are given an array weights where weights[i] represents the weight of the i-th package on a conveyor belt. All the packages must be shipped in the order given from one port to another within days days.

Each day, the ship can carry a contiguous sequence of packages, as long as the total weight does not exceed its maximum capacity.

Your task is to find the minimum possible capacity of the ship so that all packages can be shipped within the given number of days.

Input: weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5 **Output: **15 Explanation: Minimum ship capacity = 15. One way to ship in 5 days:

Day 1: 1 + 2 + 3 + 4 + 5 = 15
Day 2: 6 + 7 = 13
Day 3: 8
Day 4: 9
Day 5: 10

No day exceeds capacity 15 and all packages are shipped in order in 5 days.

**Input: **weights = [3, 2, 2, 4, 1, 4], days = 3 **Output: **6 Explanation: One possible division with capacity 6:

Day 1: 3 + 2 = 5
Day 2: 2 + 4 = 6
Day 3: 1 + 4 = 5

All packages shipped in order within 3 days.

**Input: **weights = [10, 50, 50, 10], days = 2

1 <= days <= weights.length <= 5 * 10⁴
1 <= weights[i] <= 500

cpp

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int days) {
        // Your code goes here
    }
};

java

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        // Your code goes here
    }
}

python

class Solution:
    def shipWithinDays(self, weights, days):
        # Your code goes here

javascript

class Solution {
    shipWithinDays(weights, days) {
        // Your code goes here
    }
}

csharp

public class Solution
{
    public int ShipWithinDays(int[] weights, int days)
    {
        // Your code goes here
    }
}

func shipWithinDays(weights []int, days int) int {

Stuck? Show a way to structure it+

01Bound capacity between the heaviest package and the sum of all packages.
02For a candidate capacity, greedily fill each day in order and count required days.
03Move the upper bound down when the schedule fits within the allowed days.
04Return the first feasible capacity while preserving package order in the check.

Reference answer

The minimum capacity is at least the heaviest package and at most the sum of all weights. Binary-search this integer range. To test a candidate capacity, scan packages in order with a running daily load. Add the next package if it fits; otherwise start a new day with that package. This greedy packing minimizes the number of days for the chosen capacity because delaying a package cannot make an earlier day fuller or reduce later work. If required days are at most the limit, the capacity is feasible and search left; otherwise search right. Return the smallest feasible capacity. Each check is O(n), and binary search performs O(log(sum - max + 1)) checks, with O(1) extra space. Package order must remain unchanged, so sorting weights would solve a different problem.

Then expect these follow-ups

Why does greedy day filling minimize days for a fixed capacity?
Tests: predicate proof
How would you output the daily package groups?
Tests: reconstruction

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question