Capacity To Ship Packages Within D Days

Capacity To Ship Packages Within D Days is the twin of Split Array Largest Sum. Same trick, friendlier story. You load packages onto a ship and you want the smallest ship that still finishes in time. The interviewer wants to see if you spot that this is “binary search on the answer” wearing a shipping costume.

🎯 The Problem

You load packages onto a ship and you want the smallest ship that still finishes in time. Here are the rules.

• Each package on the belt has a weight.
• Packages ship in belt order. You cannot reorder them.
• You get a number of days days.
• Each day the ship loads from the front of the belt, in order, without going over its weight capacity.
• Capacity is the most weight the ship can carry in one day.
• Find the smallest capacity that ships everything within days days.

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

Explanation: With capacity 15 the days are:
Day 1: 1, 2, 3, 4, 5   (sum 15)
Day 2: 6, 7            (sum 13)
Day 3: 8              (sum 8)
Day 4: 9              (sum 9)
Day 5: 10             (sum 10)
That fits in 5 days, and no smaller capacity does.

The order is fixed. You only choose the capacity. A bigger capacity finishes in fewer days. A smaller capacity needs more days. You want the smallest one that still meets the deadline.

Here is the picture. A chosen capacity decides how the packages fall into days.

🐢 Approach 1: Try Every Capacity (Brute Force)

The idea in one line: test each capacity from small to big until one ships everything in time.

The idea:

• Start at the heaviest single package. The ship must at least carry that.
• Test a capacity: simulate the loading and count the days.
• If it finishes in time, that capacity is the answer.
• If not, add one and try again.

Why it is weak:

• The capacity range can be huge, up to the total weight of all packages.
• Testing every value one at a time is slow.
• This is O(range times n) time, which crawls when weights are large.

Here is the try-every-capacity code:

def ship_within_days(weights, days):
    def can_ship(capacity):
        used_days = 1
        load = 0
        for weight in weights:
            if load + weight > capacity:
                used_days += 1
                load = 0
            load += weight
        return used_days <= days

    for capacity in range(max(weights), sum(weights) + 1):
        if can_ship(capacity):
            return capacity

⚡ Approach 2: Binary Search on the Answer (Best)

The idea in one line: the works-or-not answer flips once as capacity grows, so binary search the capacity for that flip.

The idea:

• A capacity that works means every bigger capacity also works. More room never needs more days.
• A capacity that fails means every smaller capacity also fails.
• So the answer flips exactly once. That single flip point is what binary search finds.

The search range:

• The capacity must be at least the heaviest single package, or that package never fits.
• It need not be more than the total weight, since that ships everything in one day.
• So the answer lives between those two bounds.

How it works:

• Guess a capacity in the middle.
• Run the feasibility check, a yes-or-no test: can this capacity ship everything within days days?
• The check loads greedily. Add packages until the next would overflow, then start a new day. Count the days.
• If the count is days or fewer, it works. Search the lower half for a smaller one.
• If it fails, it was too small. Search the upper half.

Why it is fast:

• Each step halves the capacity range.
• The day count is one pass of the array.
• So the time is O(n log S), where S is the total weight.

Here is a dry run on the example. Watch the capacity range narrow.

Steps to Solve

1. Set the low end of the search to the heaviest single package.
2. Set the high end to the total weight of all packages.
3. Pick the middle value cap between low and high. This is the guessed capacity.
4. Run the feasibility check: simulate loading days with this capacity and count the days needed.
5. If the count is days or fewer, the capacity works, so move high down to cap. Otherwise move low up past cap.
6. When low and high meet, low is the smallest workable capacity. Return it.

#include <stdio.h>

// days needed if the ship can carry at most cap per day
int daysNeeded(int w[], int n, int cap) {
    int days = 1, load = 0;
    for (int i = 0; i < n; i++) {
        if (load + w[i] > cap) {  // would overflow, start a new day
            days++;
            load = w[i];
        } else {
            load += w[i];
        }
    }
    return days;
}

int shipWithinDays(int w[], int n, int days) {
    int lo = 0, hi = 0;
    for (int i = 0; i < n; i++) {
        if (w[i] > lo) lo = w[i];   // heaviest single package
        hi += w[i];                 // total weight
    }
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (daysNeeded(w, n, mid) <= days) {  // capacity works
            hi = mid;                          // try smaller
        } else {
            lo = mid + 1;                      // too small, raise it
        }
    }
    return lo;
}

int main(void) {
    int w[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    printf("%d\n", shipWithinDays(w, 10, 5));
    return 0;
}

15

#include <iostream>
#include <vector>
using namespace std;

int daysNeeded(vector<int>& w, int cap) {
    int days = 1, load = 0;
    for (int x : w) {
        if (load + x > cap) {   // would overflow, new day
            days++;
            load = x;
        } else {
            load += x;
        }
    }
    return days;
}

int shipWithinDays(vector<int>& w, int days) {
    int lo = 0, hi = 0;
    for (int x : w) {
        lo = max(lo, x);   // heaviest single package
        hi += x;           // total weight
    }
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (daysNeeded(w, mid) <= days) {
            hi = mid;       // try smaller
        } else {
            lo = mid + 1;   // too small
        }
    }
    return lo;
}

int main() {
    vector<int> w = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    cout << shipWithinDays(w, 5) << endl;
    return 0;
}

15

public class ShipPackages {
    static int daysNeeded(int[] w, int cap) {
        int days = 1, load = 0;
        for (int x : w) {
            if (load + x > cap) {   // would overflow, new day
                days++;
                load = x;
            } else {
                load += x;
            }
        }
        return days;
    }

    public static int shipWithinDays(int[] w, int days) {
        int lo = 0, hi = 0;
        for (int x : w) {
            lo = Math.max(lo, x);   // heaviest single package
            hi += x;                // total weight
        }
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (daysNeeded(w, mid) <= days) {
                hi = mid;            // try smaller
            } else {
                lo = mid + 1;        // too small
            }
        }
        return lo;
    }

    public static void main(String[] args) {
        int[] w = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println(shipWithinDays(w, 5));
    }
}

15

def days_needed(weights, cap):
    days, load = 1, 0
    for x in weights:
        if load + x > cap:   # would overflow, start a new day
            days += 1
            load = x
        else:
            load += x
    return days


def ship_within_days(weights, days):
    lo, hi = max(weights), sum(weights)   # capacity lives in this range
    while lo < hi:
        mid = (lo + hi) // 2              # guessed capacity
        if days_needed(weights, mid) <= days:   # feasibility check
            hi = mid                      # works, try a smaller capacity
        else:
            lo = mid + 1                  # too small, raise the capacity
    return lo


print(ship_within_days([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5))

15

function daysNeeded(weights, cap) {
  let days = 1, load = 0;
  for (const x of weights) {
    if (load + x > cap) {  // would overflow, new day
      days++;
      load = x;
    } else {
      load += x;
    }
  }
  return days;
}

function shipWithinDays(weights, days) {
  let lo = Math.max(...weights);
  let hi = weights.reduce((a, b) => a + b, 0);
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (daysNeeded(weights, mid) <= days) {
      hi = mid;        // works, try smaller
    } else {
      lo = mid + 1;    // too small
    }
  }
  return lo;
}

console.log(shipWithinDays([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5));

15

Let us read the Python version line by line, since the day count plus the search is the full answer.

def days_needed(weights, cap):
    days, load = 1, 0
    for x in weights:
        if load + x > cap:
            days += 1
            load = x
        else:
            load += x
    return days


def ship_within_days(weights, days):
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if days_needed(weights, mid) <= days:
            hi = mid
        else:
            lo = mid + 1
    return lo

days, load = 1, 0 starts the day count at one open day with nothing loaded yet. There is always at least one day.

if load + x > cap asks if loading this package would push today over the capacity. If yes, today is full, so we start a new day with days += 1 and put the package on the fresh day with load = x. If no, we keep loading with load += x. This greedy loading uses the fewest days for that capacity.

return days gives the smallest number of days this capacity needs.

lo, hi = max(weights), sum(weights) sets the capacity range. The capacity must hold the heaviest single package, and never needs to be more than the total weight. So the answer sits between them.

while lo < hi shrinks the range until the two ends meet on the answer.

mid = (lo + hi) // 2 is the guessed capacity for this round.

if days_needed(weights, mid) <= days runs the feasibility check. If this capacity ships everything within the deadline, it works. So hi = mid tests whether an even smaller capacity also works. We keep mid in the range because it might be the final answer.

else: lo = mid + 1 runs when the capacity needs too many days. It was too small, so we raise the floor past it.

return lo gives the smallest capacity that still meets the deadline.

⏱️ Time and Space Complexity

The brute force steps through every capacity value, so it is O(range times n) and crawls for large weights. The binary search runs the day count, which is one pass of the array, inside a loop that halves a numeric range. So the time is O(n log S), where n is the package count and S is the total weight. It uses only a few variables, so space is O(1).

🧩 Key Takeaways

• ✅ We search the range of possible capacities, not the package list.
• ✅ The capacity sits between the heaviest single package and the total weight.
• ✅ The feasibility check greedily loads days and counts how many a capacity needs.
• ✅ If a capacity meets the deadline, try a smaller one. If not, raise it.
• ✅ This runs in O(n log S) time with only O(1) extra space.

🚀 What’s Next?

• Split Array Largest Sum
• Time Based Key-Value Store