Capacity to Ship Packages Within D Days

Medium
815.

Capacity to Ship Packages Within D Days

Capacity to Ship Packages Within D Days is a medium coding problem on arrays and binary search, asked in Amazon, Google, Flipkart and Myntra interviews.

Packages must be shipped in the given order within days days. Each day you load the ship with consecutive packages without exceeding its weight capacity.

Return the minimum capacity that gets every package shipped in time.

Example 1

Input
weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output
15
Explanation
Days of 1+2+3+4+5, 6+7, 8, 9, 10.

Example 2

Input
weights = [3,2,2,4,1,4], days = 3
Output
6

Example 3

Input
weights = [1,2,3,1,1], days = 4
Output
3

Constraints

  • 1 <= days <= weights.length <= 50000
  • 1 <= weights[i] <= 500
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} weights
 * @param {number} days
 * @return {number}
 */
var shipWithinDays = function(weights, days) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Capacity to Ship Packages Within D Days — Problem & Solution

Capacity to Ship Packages Within D Days solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Capacity to Ship Packages Within D Days is a medium coding problem on arrays and binary search, asked in Amazon, Google, Flipkart and Myntra interviews.

Problem statement

Packages must be shipped in the given order within days days. Each day you load the ship with consecutive packages without exceeding its weight capacity.

Return the minimum capacity that gets every package shipped in time.

Example 1

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
Explanation: Days of 1+2+3+4+5, 6+7, 8, 9, 10.

Example 2

Input: weights = [3,2,2,4,1,4], days = 3
Output: 6

Example 3

Input: weights = [1,2,3,1,1], days = 4
Output: 3

Constraints

  • 1 <= days <= weights.length <= 50000
  • 1 <= weights[i] <= 500

Hints for Capacity to Ship Packages Within D Days

  1. Hint 1

    If a capacity works, every larger capacity works too — the feasibility is monotone.

  2. Hint 2

    So binary search the capacity, and for each candidate greedily count the days needed.

  3. Hint 3

    The search range runs from the heaviest single package to the total weight.

How to solve Capacity to Ship Packages Within D Days

Binary search on the answer. For a fixed capacity, the minimum number of days is obtained greedily — keep loading while it fits — and that count is non-increasing in the capacity, so the feasible capacities form a suffix.

Approach

  1. Set lo to the maximum weight (anything smaller cannot carry that package) and hi to the total weight (one day suffices).
  2. need(cap): sweep the weights, starting a new day whenever the next package would overflow.
  3. Binary search the smallest cap with need(cap) <= days.

Why it works

The greedy day count is optimal for a fixed capacity: deferring a package that fits can only push work later and never reduces the number of days. Raising the capacity can only let more packages fit per day, so need is non-increasing — exactly the monotonicity binary search needs.

Complexity

  • Time — O(n log W) where W is the total weight
  • Space — O(1)

Pitfalls

  • Starting lo at 1 lets the search consider capacities that can never carry the heaviest package; need must then be written not to loop forever.
  • d starts at 1, not 0 — the first day is already in use.
  • Splitting packages or reordering them is not allowed.

Reference solution

Python

from typing import List

def shipWithinDays(weights: List[int], days: int) -> int:
    lo, hi = max(weights), sum(weights)

    def need(cap: int) -> int:
        d, cur = 1, 0
        for w in weights:
            if cur + w > cap:
                d += 1
                cur = 0
            cur += w
        return d

    while lo < hi:
        mid = (lo + hi) // 2
        if need(mid) <= days:
            hi = mid
        else:
            lo = mid + 1
    return lo

Java

private static int daysNeeded(int[] weights, int cap) {
    int d = 1, cur = 0;
    for (int w : weights) {
        if (cur + w > cap) {
            d++;
            cur = 0;
        }
        cur += w;
    }
    return d;
}

public static int shipWithinDays(int[] weights, int days) {
    int lo = 0, hi = 0;
    for (int w : weights) {
        lo = Math.max(lo, w);
        hi += w;
    }
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (daysNeeded(weights, mid) <= days) hi = mid; else lo = mid + 1;
    }
    return lo;
}

C++

static int daysNeeded(vector<int>& weights, int cap) {
    int d = 1, cur = 0;
    for (int w : weights) {
        if (cur + w > cap) {
            d++;
            cur = 0;
        }
        cur += w;
    }
    return d;
}

int shipWithinDays(vector<int>& weights, int days) {
    int lo = 0, hi = 0;
    for (int w : weights) {
        lo = max(lo, w);
        hi += w;
    }
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (daysNeeded(weights, mid) <= days) hi = mid; else lo = mid + 1;
    }
    return lo;
}

JavaScript

var shipWithinDays = function(weights, days) {
    var lo = 0, hi = 0, i;
    for (i = 0; i < weights.length; i++) {
        if (weights[i] > lo) lo = weights[i];
        hi += weights[i];
    }
    var need = function(cap) {
        var d = 1, cur = 0;
        for (var j = 0; j < weights.length; j++) {
            if (cur + weights[j] > cap) { d++; cur = 0; }
            cur += weights[j];
        }
        return d;
    };
    while (lo < hi) {
        var mid = Math.floor((lo + hi) / 2);
        if (need(mid) <= days) hi = mid; else lo = mid + 1;
    }
    return lo;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search