Maximum Units on a Truck — Solution

Problem

You have a truck with a limited number of box slots. Each box type has a count of available boxes and a fixed number of units inside each box. Your goal is to choose which boxes to load so that the total number of units on the truck is as large as possible.

Example:

• Input: boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
• Output: 8
• Explanation: Load the 1 box with 3 units, both boxes with 2 units each (4 units), and 1 of the boxes with 1 unit — that fills 4 slots for a total of 8 units.

Counter-example: If you loaded the 3 boxes with 1 unit each first, you'd use 3 slots for only 3 units — leaving less room for the more valuable box types.

Intuition

The key observation is that every box takes exactly one truck slot, regardless of how many units it holds. This means you should always prefer the box type with the most units per box — it gives you the highest return per slot. Sort by units-per-box descending, then greedily fill the truck from the top.

Solution — Greedy Sort

Sort box types by units per box in descending order, then iterate and take as many boxes as possible from each type until the truck is full.

1. Sort boxTypes by unitsPerBox in descending order.
2. Initialize total_units = 0 and remaining_capacity = truckSize.
3. For each box type, calculate how many boxes to take: min(numberOfBoxes, remaining_capacity).
4. Add boxes_taken × unitsPerBox to total_units and reduce remaining_capacity.
5. Stop early if remaining_capacity reaches 0.
6. Return total_units.

1def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
2    # Sort by units per box descending — highest value per slot first
3    boxTypes.sort(key=lambda box: box[1], reverse=True)
4
5    total_units = 0
6    remaining_capacity = truckSize
7
8    for num_boxes, units_per_box in boxTypes:
9        # Can't exceed truck capacity, so cap at what's left
10        boxes_to_take = min(num_boxes, remaining_capacity)
11        total_units += boxes_to_take * units_per_box
12        remaining_capacity -= boxes_to_take
13
14        if remaining_capacity == 0:
15            break
16
17    return total_units

Time: O(n log n) — dominated by sorting; the greedy scan afterward is O(n).

Space: O(1) — sorting is in-place and only a few scalar variables are used.

Complexity Summary

Common Mistakes

• Sorting by numberOfBoxes instead of unitsPerBox — more boxes of a type doesn't mean more value per truck slot; the units column is what determines priority.
• Sorting in ascending order — this loads the least valuable boxes first, minimizing total units rather than maximizing them.
• Taking all boxes of a type regardless of remaining capacity — when the truck is nearly full, you must cap with min(numberOfBoxes, remainingCapacity) or you'll overload it.
• Confusing box[0] and box[1] — box[0] is the count of boxes, box[1] is units per box; mixing these up either sorts on the wrong key or computes wrong unit totals.
• Skipping the early-exit check — not breaking when remainingCapacity == 0 still produces the correct answer but wastes iterations; more importantly, omitting it during a review signals you haven't reasoned about when the loop can stop.

Related Problems

• boats-to-save-people — greedy selection with a per-slot constraint
• k-closest-points-to-origin — selection problem where you sort on a derived key to pick the best candidates
• last-stone-weight — greedy with a priority queue for repeated max selection
• candy — greedy problem requiring you to distribute resources optimally under constraints
• largest-number — custom comparator sort to maximize a value, same core idea as sorting by units-per-box