Maximum Units on a Truck — Solution in Python, Java & C++
Maximum Units on a Truck solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Maximum Units on a Truck is an easy coding problem on arrays, sorting and greedy, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Sorting, Greedy
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are loading boxes onto one truck. boxTypes[i] = [count, unitsPerBox] means there are count boxes of that type and each holds unitsPerBox units.
You may load at most truckSize boxes in total, choosing any combination. Return the maximum total number of units you can carry.
Example 1
Input: boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
Output: 8
Explanation: Take the 1 box of 3 units, both boxes of 2 units, and one box of 1 unit.
Example 2
Input: boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
Output: 91
Example 3
Input: boxTypes = [[1,1]], truckSize = 5
Output: 1
Constraints
1 <= boxTypes.length <= 301 <= count, unitsPerBox <= 10001 <= truckSize <= 1000
Hints for Maximum Units on a Truck
Hint 1
Every box takes the same amount of truck space, so always prefer the box that carries more units.
Hint 2
Sort by units per box descending and take greedily until the truck is full.
Hint 3
The last box type may be taken only partially — clamp the count to the remaining space.
How to solve Maximum Units on a Truck
Every box occupies one slot, so fill the truck with the highest-units boxes first.
Approach
- Sort box types by units per box descending.
- For each type, take
min(remaining, count)boxes and add their units; stop when the truck is full.
Why it works
Replacing any loaded box with an unloaded box of higher units never reduces the total, so the greedy order is optimal (a fractional knapsack with unit weights).
Complexity
- Time —
O(n log n) - Space —
O(1) beyond the sort
Pitfalls
- The last type may be taken partially — clamp to the remaining slots.
Reference solution
Python
def maximumUnits(boxTypes, truckSize: int) -> int:
ordered = sorted(boxTypes, key=lambda b: -b[1])
remaining = truckSize
total = 0
for count, units in ordered:
if remaining <= 0:
break
take = min(remaining, count)
total += take * units
remaining -= take
return totalJava
public static int maximumUnits(int[][] boxTypes, int truckSize) {
int[][] s = boxTypes.clone();
Arrays.sort(s, (a, b) -> b[1] - a[1]);
int remaining = truckSize, total = 0;
for (int i = 0; i < s.length && remaining > 0; i++) {
int take = Math.min(remaining, s[i][0]);
total += take * s[i][1];
remaining -= take;
}
return total;
}C++
int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
vector<vector<int>> s = boxTypes;
sort(s.begin(), s.end(), [](const vector<int>& a, const vector<int>& b) { return a[1] > b[1]; });
int remaining = truckSize, total = 0;
for (int i = 0; i < (int) s.size() && remaining > 0; i++) {
int take = min(remaining, s[i][0]);
total += take * s[i][1];
remaining -= take;
}
return total;
}JavaScript
var maximumUnits = function(boxTypes, truckSize) {
const sorted = boxTypes.slice().sort(function(a, b) { return b[1] - a[1]; });
let remaining = truckSize, total = 0;
for (let i = 0; i < sorted.length && remaining > 0; i++) {
const take = Math.min(remaining, sorted[i][0]);
total += take * sorted[i][1];
remaining -= take;
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms