Maximum Units on a Truck: Greedy Sorting

June 3, 20264 min read

leetcodeproblemeasyarrayssortinggreedy

You are given an array of box types where each entry is [numberOfBoxes, numberOfUnitsPerBox], and an integer truckSize representing the maximum number of boxes the truck can carry. Each box takes exactly one slot on the truck regardless of how many units it holds. Your goal is to maximize the total number of units loaded onto the truck.

This is LeetCode 1710: Maximum Units on a Truck, an easy problem that teaches the greedy sorting pattern. Because every box occupies the same amount of space, you always want to pick the boxes that carry the most units first.

boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4. Load the highest-unit boxes first: 1 box of 3 units, 2 boxes of 2 units, 1 box of 1 unit. Total = 8.

Approach: greedy by units per box

Every box takes up exactly one slot on the truck, no matter how many units it contains. That means a box with 3 units is always more valuable than a box with 1 unit, and they cost the same in terms of capacity. So the strategy is simple: sort the box types by numberOfUnitsPerBox in descending order, then greedily load boxes from the most valuable type first. For each type, take as many boxes as you can (either the full count or whatever capacity remains, whichever is smaller). Once the truck is full, stop.

This works because there is no trade-off between box types. Taking a high-unit box never prevents you from making a better choice later. It is the optimal greedy choice at every step.

def maximumUnits(boxTypes, truckSize):
    boxTypes.sort(key=lambda x: -x[1])
    total = 0
    for count, units in boxTypes:
        take = min(count, truckSize)
        total += take * units
        truckSize -= take
        if truckSize == 0:
            break
    return total

Practice this problem with spaced repetition

Visual walkthrough

Step 1: Sort boxTypes by units per box (descending).

Already sorted in this example. In general, sort by the second element descending: 3 > 2 > 1.

Step 2: Process type [1,3]. Take min(1, 4) = 1 box.

1 box loaded carrying 3 units. Remaining capacity: 4 - 1 = 3. Running total: 3 units.

Step 3: Process type [2,2]. Take min(2, 3) = 2 boxes.

2 more boxes loaded, each carrying 2 units. Remaining capacity: 3 - 2 = 1. Running total: 3 + 4 = 7 units.

Step 4: Process type [3,1]. Take min(3, 1) = 1 box.

Only 1 slot left, so we take 1 of the 3 available boxes. Remaining capacity: 0. Running total: 7 + 1 = 8 units.

Step 5: Truck is full. Return 8.

No more capacity. The maximum total units we can load is 8.

The truck fills up after processing all three box types. We loaded 1 box of 3 units, 2 boxes of 2 units, and 1 box of 1 unit. The total is 3 + 4 + 1 = 8, which is the maximum possible.

Complexity analysis

Approach	Time	Space
Greedy sort	O(n log n)	O(1) (or O(n) for sort)

Sorting dominates the runtime at O(n log n), where n is the number of box types. The iteration afterwards is O(n). Space depends on whether your language sorts in place. Python's sort() uses O(n) auxiliary space in the worst case, but some implementations treat it as O(1) since the input is modified in place.

Building blocks

1. Greedy selection by value density

This problem is a simplified version of the fractional knapsack. In the classic fractional knapsack, items have different weights and values, and you pick by value-per-weight ratio. Here, every box has weight 1, so the "density" is just the number of units. The greedy rule becomes: always pick the item with the highest value density first.

items.sort(key=lambda x: -value_density(x))
remaining = capacity
total = 0
for item in items:
    take = min(item.count, remaining)
    total += take * item.value
    remaining -= take

This pattern applies whenever you have a fixed capacity and items of equal "cost" but different values. Sort by value, take greedily.

2. Sort-then-iterate

Many greedy problems follow the same two-phase structure: sort the input by some key, then make a single pass through the sorted data collecting the answer.

data.sort(key=sorting_criterion)
result = initial_value
for item in data:
    result = update(result, item)
return result

In this problem, the sorting criterion is units per box (descending), and the update step loads boxes until the truck is full. You will see this exact skeleton in problems like Assign Cookies, Meeting Rooms, and Boats to Save People.

Build your pattern library with CodeBricks

Edge cases

Truck can fit all boxes: just sum everything. The loop finishes without truckSize hitting zero, and you return the total of all boxes times their units.
Single box type: take min(count, truckSize) boxes of that type.
truckSize = 0: the loop body never executes (or take is always 0), so return 0.

From understanding to recall

You have read the greedy solution and it clicks. Sort by units per box, take the most valuable boxes first, stop when the truck is full. But in an interview, the details matter. Do you sort ascending or descending? Do you use min(count, truckSize) or an if-statement? Do you remember to subtract from truckSize?

Spaced repetition helps you internalize these details so they flow out automatically under pressure. You write the sort-then-iterate loop from scratch at increasing intervals until it becomes second nature. The greedy-by-density pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems.

Start drilling with CodeBricks

Assign Cookies - another greedy assignment problem
Lemonade Change - greedy decision making
Array Partition - sorting-based greedy optimization