1710 - Maximum Units on a Truck

Difficulty: Easy | Pattern: Greedy / Sorting | Company tags: Amazon, Facebook

Problem Statement

You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxes_i, numberOfUnitsPerBox_i]:

• numberOfBoxes_i: the number of boxes of type i.
• numberOfUnitsPerBox_i: the number of units in each box of type i.

You are also given an integer truckSize, which is the maximum number of boxes that can be put on the truck. You can choose any boxes to put on the truck as long as the number doesn't exceed truckSize.

Return the maximum total number of units that can be put on the truck.

Example 1:

Input: boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
Output: 8
Explanation: Take 1 box of type 0 (3 units), 2 boxes of type 1 (4 units), 1 box of type 2 (1 unit) = 8

Example 2:

Input: boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
Output: 91

Approach: Greedy — O(n log n)

Key insight: Sort box types by units per box in descending order. Take as many boxes as possible from the highest unit type first.

def maximumUnits(boxTypes: list[list[int]], truckSize: int) -> int:
    # Sort by units per box descending
    boxTypes.sort(key=lambda x: x[1], reverse=True)
    
    total_units = 0
    remaining = truckSize
    
    for count, units in boxTypes:
        take = min(count, remaining)
        total_units += take * units
        remaining -= take
        if remaining == 0:
            break
    
    return total_units

Algorithm Flow

Dry Run

boxTypes = [[1,3],[2,2],[3,1]], truckSize=4

After sort (desc by units): [[1,3],[2,2],[3,1]] (already sorted)

count	units	take	total
1	3	min(1,4)=1	1×3=3
2	2	min(2,3)=2	3+4=7
3	1	min(3,1)=1	7+1=8

Output: 8 ✓

Edge Cases

• truckSize >= total boxes → take everything
• Single box type → take min(count, truckSize) boxes

Complexity

• Time: O(n log n) for sorting
• Space: O(1)

This is a variant of the classic greedy fractional knapsack problem — but here boxes are indivisible, so we take integer counts. However, since unit costs are the same per box, greedy still works.

Key Terms

Term	Definition
Greedy algorithm	Makes the locally optimal choice (highest units-per-box first) at each step, which here yields a global optimum.
Exchange argument	Proof technique showing that swapping a lower-value choice for a higher-value one never decreases the result — justifies greedy correctness.
Sorting-based greedy	A greedy strategy that first sorts inputs by a key criterion, then processes them in that order.
Fractional knapsack	Classic problem where greedy-by-ratio is provably optimal because items are divisible (or, as here, uniform in value per unit of capacity).

FAQ

1. Can this be solved without extra space beyond O(1)? Sorting itself needs O(log n) to O(n) auxiliary space depending on the sort implementation, but no additional data structures are needed beyond that.
2. What if boxTypes is empty? Return 0 immediately since there's nothing to load.
3. What if truckSize is 0? The loop's take = min(count, remaining) is always 0, so total_units stays 0.
4. Why does greedy work here instead of needing DP? Because each box of a given type contributes the same fixed units-per-box regardless of order, taking the highest-value boxes first never blocks a better combination later — there's no trade-off to weigh, unlike 0/1 knapsack.
5. How would this change if boxes had a weight in addition to a count constraint? It becomes closer to a real knapsack problem (bounded knapsack) and greedy alone would no longer guarantee optimality — DP would be needed.

Quick Revision

• Pattern: greedy with sorting by a value-density key.
• Sort boxTypes by unitsPerBox descending.
• Walk sorted list, greedily fill truck with as many boxes as possible from the current highest-value type.
• Stop early once remaining == 0.
• Track total_units and remaining capacity.
• Time: O(n log n) for the sort; the fill loop itself is O(n).
• Space: O(1) extra (in-place sort aside).
• Correctness: uniform per-box value means no exchange can improve on taking higher units-per-box first.
• Edge cases: empty input → 0; truckSize ≥ total boxes → take everything.

Related Problems

• Fractional knapsack pattern: classic greedy-by-ratio problems.
• 455-AssignCookies.md — greedy matching by sorting both sequences.
• 435-NonOverlappingIntervals.md — another sort-then-greedy problem.