Generated by Codex with GPT-5

Quick facts

Problem gist

There is a line of packages, each with a weight. A ship moves packages in the given order, and each day it can carry packages only until the total loaded weight reaches its capacity. The task is to find the smallest ship capacity that can move every package within days days.

The order constraint is the key detail. The ship cannot sort or choose arbitrary packages; it must take a prefix of the remaining packages each day. That turns the problem into choosing where to split the array into at most days contiguous groups while minimizing the largest group sum.

Deriving the optimal solution

A direct dynamic programming view is possible: split the array into days and minimize the heaviest day. But the simpler interview solution starts with a different question:

Given a proposed capacity, can the ship finish on time?

That check is easy. Walk through the weights from left to right, adding each package to the current day while it fits. When the next package would exceed the capacity, start a new day. If the number of days used is at most days, the capacity works.

This greedy check is enough because, for a fixed capacity, filling the current day as much as possible never makes the future worse. It only leaves fewer packages for later days. Starting a new day earlier cannot increase the remaining capacity on future days, so it cannot reduce the number of days needed.

Why binary search fits

The feasibility check is monotonic:

  • If capacity C works, any larger capacity also works.
  • If capacity C fails, any smaller capacity also fails.

So the answer is the first capacity where the predicate changes from “too small” to “large enough.”

The search bounds are natural:

  • The capacity must be at least max(weights), because every package must fit on the ship by itself.
  • The capacity never needs to exceed sum(weights), because that ships everything in one day.

A slightly tighter lower bound is ceil(sum(weights) / days), because the total weight must be spread across the available days. The real lower bound is the maximum of that average and the heaviest single package.

Small example

For weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and days = 5, try capacity 15.

The greedy schedule is:

  • Day 1: [1, 2, 3, 4, 5]
  • Day 2: [6, 7]
  • Day 3: [8]
  • Day 4: [9]
  • Day 5: [10]

Capacity 15 works. Capacity 14 fails because the same greedy process needs six days. Since feasibility only improves as capacity grows, the minimum valid capacity is 15.

Python solution

from typing import List


def days_needed_for_capacity(weights: List[int], capacity: int) -> int:
    """
    Return the minimum number of days needed when the ship has the given
    capacity and packages must be shipped in their original order.
    """
    days_used = 1
    current_day_load = 0

    for package_weight in weights:
        # If this package would overflow today's load, it must start
        # tomorrow's contiguous shipment group.
        if current_day_load + package_weight > capacity:
            days_used += 1
            current_day_load = 0

        current_day_load += package_weight

    return days_used


def can_ship_with_capacity(weights: List[int], days: int, capacity: int) -> bool:
    """Return whether all packages can be shipped within the day limit."""
    return days_needed_for_capacity(weights, capacity) <= days


def minimum_ship_capacity(weights: List[int], days: int) -> int:
    """
    Binary search for the smallest ship capacity that finishes all packages
    within the requested number of days.
    """
    if days <= 0:
        raise ValueError("days must be positive")
    if not weights:
        return 0

    total_weight = sum(weights)
    heaviest_package = max(weights)

    left = max(heaviest_package, (total_weight + days - 1) // days)
    right = total_weight

    while left < right:
        middle_capacity = left + (right - left) // 2

        if can_ship_with_capacity(weights, days, middle_capacity):
            right = middle_capacity
        else:
            left = middle_capacity + 1

    return left


class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        return minimum_ship_capacity(weights, days)

Complexity

Each feasibility check scans the weights once, so it costs O(n).

The binary search checks O(log S) capacities, where S is the search range between the lower bound and sum(weights). The total time complexity is O(n log S), and the extra space complexity is O(1).

Interview follow-ups

Why is the greedy feasibility check correct?

For a fixed capacity, the greedy check always puts the next package on the current day if it fits. This is optimal because the package order is fixed and every day has the same capacity. Shipping fewer packages today only leaves more packages for later, and it does not create extra capacity on those later days.

The proof can be phrased as an exchange argument. If some valid schedule starts a new day while the next package still fits today, moving that package into the earlier day keeps all day loads within capacity and cannot make later days harder. Repeating that move turns the schedule into the greedy one without using more days. So if greedy needs too many days, no schedule with that capacity can work.

How would the solution return an actual shipping schedule?

First compute the minimum capacity with the binary search. Then run the same left-to-right greedy pass again and collect each day’s package group whenever adding the next package would exceed that capacity.

If the interviewer requires exactly days groups rather than at most days, split some non-empty groups during the reconstruction pass. Splitting a group never increases any group sum, so it remains valid under the same capacity. The capacity search is still O(n log S), and building the schedule adds O(n) time plus O(n) output space.

What changes if packages may be reordered?

The problem becomes much harder. With reordering, a fixed-capacity feasibility check asks whether the weights can be packed into at most days bins of equal capacity. That is a bin-packing style problem, which is computationally hard in general.

The original ordered version is easier because each day must take a contiguous slice of the array. That structure makes the greedy feasibility check exact. Without that structure, greedy packing rules are heuristics unless the constraints are small enough for backtracking or dynamic programming over subsets.

Can dynamic programming solve the ordered version?

Yes. The ordered problem is closely related to splitting an array into contiguous parts while minimizing the largest part sum. A dynamic programming solution can define dp[d][i] as the minimum possible largest day load for shipping the first i packages in d days, then try every previous split point.

That approach is useful for teaching the partitioning structure, but its straightforward form costs O(days * n^2) time. The binary search solution is usually preferred because the feasibility check is simple and the total runtime is O(n log S).

Why not binary search the number of days instead?

The number of days is fixed by the problem; the unknown value is capacity. More importantly, the direct feasibility predicate answers “does this capacity fit within the fixed day limit?” That predicate is monotonic in capacity, which is exactly what binary search needs.

Trying to search over days would answer a different question: for a fixed capacity, how many days are needed? The algorithm already computes that value inside the feasibility check, but it does not identify the smallest capacity unless capacity is the searched dimension.

Practical takeaway

The main move is to turn the scheduling problem into a yes-or-no capacity test. Once a proposed capacity can be checked greedily, the monotonic boundary becomes visible, and binary search finds the smallest valid capacity without exploring every possible shipment split.