Maximum Units on a Truck
Asked at JPMorgan
Problem
Maximum Units on a Truck gives you box types (how many boxes of that type exist and how many units each box holds) and a truck that fits truckSize boxes. Maximize the total units loaded. Every box takes the same space, so load the richest boxes first.
Asked At
| Company | Difficulty | |
|---|---|---|
| JPMorgan | Easy | View all JPMorgan questions → |
How to Think About It
Every box occupies one slot regardless of type, so each slot should hold the box with the most units available.
Sort box types by units per box, descending.
Walk the sorted list: take min(count, remaining capacity) boxes of each type, add their units, and reduce the capacity. Stop when the truck is full.
Walkthrough: [[1,3],[2,2],[3,1]], truck size 4. Take 1 box of 3 units, 2 boxes of 2 units, then 1 box of 1 unit -> 3 + 4 + 1 = 8.
Since units per box are at most 1000, a counting sort over unit values gives O(n + 1000) if the interviewer asks for better than O(n log n).
Optimal Approach
Step 1: Sort boxTypes by units per box descending.
Step 2: total = 0.
Step 3: For each (count, units): take = min(count, truckSize); total += take * units; truckSize -= take; stop if truckSize == 0.
Step 4: Return total.
Time: O(n log n). Space: O(1) extra.
What Trips People Up in Real Interviews
Sorting by the number of boxes instead of units per box.
Taking every box of a type even when the truck has less room left.
Treating it like a 0/1 knapsack. Every box has the same size, so greedy is optimal.
Not stopping once the truck is full — harmless, but it shows you did not think about the loop exit.
Solution Code
def maximumUnits(boxTypes, truckSize):
boxTypes.sort(key=lambda b: -b[1])
total = 0
for count, units in boxTypes:
take = min(count, truckSize)
total += take * units
truckSize -= take
if truckSize == 0:
break
return totalFrequently Asked Questions
What is the Maximum Units on a Truck problem?
Maximum Units on a Truck gives you box types (how many boxes of that type exist and how many units each box holds) and a truck that fits `truckSize` boxes. Maximize the total units loaded. Every box takes the same space, so load the richest boxes first.
How do you solve Maximum Units on a Truck?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Maximum Units on a Truck?
Maximum Units on a Truck is asked at JPMorgan. It is a easy difficulty problem.
What are common mistakes on Maximum Units on a Truck?
- Sorting by the number of boxes instead of units per box.
- Taking every box of a type even when the truck has less room left.
- Treating it like a 0/1 knapsack. Every box has the same size, so greedy is optimal.
- Not stopping once the truck is full — harmless, but it shows you did not think about the loop exit.