Abstract / Summary

Find the minimum capacity needed to ship all packages in at most d days without splitting packages.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 74% (1+ million submissions).

Typical patterns to solve this problem:

• Array
• Binary Search

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the classic “capacity to ship packages within a given number of days” problem. It receives a list of integer weights and an integer days, and returns the minimal ship capacity that allows all packages to be delivered within the specified number of days. The algorithm works by iteratively adjusting a candidate capacity until it satisfies the day constraint.

Key Steps

The function begins by handling the trivial situation where all packages must be shipped in a single day. In that case the required capacity is simply the sum of all weights.

if days == 1:
    return sum(weights)

Next, the algorithm establishes a lower bound for the capacity, which is the heaviest single package. This ensures that any candidate capacity is at least large enough to carry the biggest weight.

capacity = max(weights)

The core of the solution is an infinite loop that evaluates whether the current capacity can accommodate the shipment schedule within the allowed days. Inside the loop, three variables are reset for each trial:

• have tracks the cumulative weight loaded onto the current ship.
• need records the smallest overload encountered during the scan, which will become the next candidate capacity if the current one fails.
• duration counts how many ships (or days) have been used so far.

while True:
    have = 0            # load of current boat
    need = float("inf") # lowest excess of overloaded boats
    duration = 1

The algorithm then iterates over each weight in the input list, adding it to the current load. When the load exceeds the candidate capacity, an overload is detected. At that moment, need is updated with the minimum of its current value and the overloaded amount (have). The load is reset to the current weight, representing the start of a new ship, and duration is incremented. If the number of ships already exceeds the allowed days, the inner loop terminates early because the candidate capacity is insufficient.

    for w in weights:
        have += w
        # overload
        if have > capacity:
            need = min(need, have)
            have = w
            duration += 1
            if duration > days:
                break

After scanning all weights, the algorithm checks whether the number of ships used (duration) fits within the required days. If it does, the current capacity is the minimal feasible value and is returned.

    # done
    if duration <= days:
        return capacity

If the capacity was insufficient, the algorithm updates capacity to the smallest overload recorded (need). This new value is guaranteed to be larger than the previous capacity but no larger than necessary, guiding the search toward the minimal feasible capacity.

    capacity = need

The loop repeats until a suitable capacity is found.

Edge Cases Handled

The implementation explicitly addresses the scenario where all packages must be shipped in a single day. By returning the total sum of weights, it avoids unnecessary computation for this extreme case.

Another implicit edge case is when the list contains a single package. In that situation max(weights) equals the package weight, and the while-loop will immediately satisfy the day constraint, returning that weight as the minimal capacity.

The use of float("inf") for need ensures that, even if no overload occurs during the scan (which can happen when the initial capacity already satisfies the day limit), the variable holds a safe sentinel value. The subsequent assignment capacity = need is only reached when an overload has been recorded, guaranteeing that capacity is always updated to a meaningful integer.

Performance Optimizations

The algorithm avoids a binary search over the capacity range, which is a common alternative. Instead, it leverages the observed overload amount (need) to jump directly to the next plausible capacity. By selecting the smallest overloaded load encountered, the search space is reduced dramatically after each iteration, often converging in very few steps.

Resetting the load (have) to the current weight at the point of overload eliminates the need to recompute the weight of the new ship from scratch. This incremental approach keeps the inner loop linear with respect to the number of packages.

Early termination of the inner loop when duration exceeds days prevents unnecessary processing of the remaining weights once it is clear that the current capacity cannot meet the constraint. This guard contributes to faster rejection of insufficient capacities, especially for large input lists.

Overall, the combination of direct capacity jumps, incremental load tracking, and early exit conditions yields an efficient solution that scales well with the size of the input list.

Imagine you have a long line of heavy toys that need to go on a boat. The boat has a specific size limit for how much weight it can carry at once. This code helps figure out the smallest boat size needed to finish moving all the toys before a certain number of days pass.

First, the code checks if there is only one day to finish the job. If there is, it puts all the toys on the boat at the same time by adding up all their weights.

If there are more days, the code starts by picking the weight of the single heaviest toy as the smallest possible size for the boat. This ensures no toy is too heavy for the boat to carry.

Next, the code starts a process of trial and error. It pretends to load the toys onto the boat one by one. It keeps adding toy weights together until the boat is full. If adding another toy would make the boat too heavy, it marks that toy for a new boat ride on the next day.

If the number of days taken to move all the toys is small enough, the boat size is just right. If it takes too many days, the boat is too small, so the code makes the boat size bigger by using the weight that caused it to be overloaded. It keeps trying this over and over until the toys can be moved within the allowed number of days.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java						TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java				Go		TS
	LeetcodeHelp	C++	Python	Java
	Progiez	C++	Python	Java
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai			Java
	everthis				JS
	Garvit244		Python
	halfrost							Go
	JoshCrozier				JS
	keineahnung2345	C++
	lkwq007		Python
	lzl124631x	C++
	MacJim	C++
	martianoff						Scala
	suxrobGM					C#
	trung-hn		Python
	varunu28			Java
	vli02								C
	vthwang			Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
Garvit244	Python
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
lzl124631x	C++
MacJim	C++
martianoff	Scala
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
vthwang	Java
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality