Smallest truck that delivers every parcel in d days

Searching sorted data Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
weights = [3, 2, 2, 4, 1, 4]

def days_for(cap: int) -> int:
    days, load = 1, 0
    for w in weights:
        if load + w > cap:
            days, load = days + 1, 0
        load += w
    return days

print(days_for(6), days_for(7), days_for(16))

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 3 3 1

Right: 6 gives [3, 2] [2, 4] [1, 4], 7 gives [3, 2, 2] [4, 1] [4], 16 takes everything at once.

Day counts never rise as capacity grows, which is the monotonic property the binary search depends on.

Why not the others?
  • B 4 3 1. At capacity 6 the parcels fit in three runs.
  • C 3 2 1. At capacity 7 the last parcel needs a third day.

30-second answer

A bigger truck never needs more days, so binary search the capacity between the heaviest parcel and the total weight. For a candidate, a greedy pass counts days by filling the truck until the next parcel would overflow. O(n log S) where S is the total weight, with O(1) extra space.

Practise saying it · 60 s. No recording, just a timer

Explain the shipping-capacity binary search.

Say your answer out loud, then check which of these points you covered:

  • Bounds: max weight to total
  • Greedy day count
  • O(n log S)

Deep dive

The lower bound max(weights) is required: a smaller truck cannot carry the heaviest parcel at all.

The greedy day count is optimal for a fixed capacity because delaying a parcel never helps.

This 'split into k groups minimising the largest group' shape appears often.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def smallest_truck(weights: list[int], days: int) -> int:
    def days_needed(cap: int) -> int:
        used, load = 1, 0
        for w in weights:
            if load + w > cap:
                used, load = used + 1, 0
            load += w
        return used

    lo, hi = max(weights), sum(weights)
    # lo: heaviest parcel, hi: everything in one day
    while lo < hi:
        mid = (lo + hi) // 2
        if days_needed(mid) <= days:
            hi = mid
        else:
            lo = mid + 1
    return lo

Common mistakes

  • Starting the search at 1 and accepting capacities below the heaviest parcel.
  • Counting days off by one when the last truckload is not counted.

Senior take & follow-ups

Name both bounds and why they are safe before writing the loop.

Follow-up questions

Think of your answer first, then open the hint.

  1. What if parcels may be reordered?

    Show hint

    Then it becomes bin packing, which is NP-hard; heuristics or search are needed.

  2. How do you return the actual daily loads?

    Show hint

    Rerun the greedy pass at the final capacity and record each day.

What each operation costs: Binary Search · Linear Search

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.