Maximum Units on a Truck
Maximum Units on a Truck is a easy arrays & hashing problem solved with the greedy pattern.
The best approach, optimal (bucket boxes by units), runs in O(n + U) time and O(U) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (repeatedly pick the best remaining type) up.
Problem
You need to load boxes onto a truck. boxTypes[i] = [numberOfBoxes_i, unitsPerBox_i] says that there are numberOfBoxes_i boxes of type i, and each of them holds unitsPerBox_i units.
The truck can carry at most truckSize boxes, whatever their type. Choose which boxes to load and return the largest total number of units the truck can carry.
Examples
Example 1
- Input
boxTypes = [[2, 5], [4, 3], [1, 8]], truckSize = 4- Output
21- Why
- Load the box with 8 units, both boxes with 5 units, and one box with 3 units: 8 + 5 + 5 + 3 = 21.
Example 2
- Input
boxTypes = [[3, 2], [3, 2]], truckSize = 10- Output
12- Why
- All 6 boxes fit, carrying 6 × 2 = 12 units.
Constraints
1 <= boxTypes.length <= 10001 <= numberOfBoxes_i, unitsPerBox_i <= 10001 <= truckSize <= 10^6
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (repeatedly pick the best remaining type) | O(n²) | O(n) |
| Sort by units, then greedy | O(n log n) | O(1) |
| Optimal (bucket boxes by units) | O(n + U) | O(U) |
1Brute force (repeatedly pick the best remaining type)
O(n²)Up to n rounds, each scanning n types.O(n)The used flags.While the truck has room, scan all box types for the one with the most units per box that still has boxes, load as many of it as fit, and mark it used.
- Keep a
usedflag per type. - While space remains: find the unused type with the largest unitsPerBox; stop if none.
- Load
take = min(count, space)boxes; addtake * units; subtract take from space; mark the type used.
class Solution {
public int maximumUnits(int[][] boxTypes, int truckSize) {
int n = boxTypes.length, space = truckSize, total = 0;
boolean[] used = new boolean[n];
while (space > 0) {
int best = -1;
for (int i = 0; i < n; i++)
if (!used[i] && (best == -1 || boxTypes[i][1] > boxTypes[best][1])) best = i;
if (best == -1) break;
used[best] = true;
int take = Math.min(boxTypes[best][0], space);
total += take * boxTypes[best][1];
space -= take;
}
return total;
}
}class Solution:
def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
n = len(boxTypes)
space, total = truckSize, 0
used = [False] * n
while space > 0:
best = -1
for i in range(n):
if not used[i] and (best == -1 or boxTypes[i][1] > boxTypes[best][1]):
best = i
if best == -1:
break
used[best] = True
take = min(boxTypes[best][0], space)
total += take * boxTypes[best][1]
space -= take
return totalclass Solution {
public:
int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
int n = boxTypes.size(), space = truckSize, total = 0;
vector<bool> used(n, false);
while (space > 0) {
int best = -1;
for (int i = 0; i < n; i++)
if (!used[i] && (best == -1 || boxTypes[i][1] > boxTypes[best][1])) best = i;
if (best == -1) break;
used[best] = true;
int take = min(boxTypes[best][0], space);
total += take * boxTypes[best][1];
space -= take;
}
return total;
}
};function maximumUnits(boxTypes, truckSize) {
const n = boxTypes.length;
let space = truckSize, total = 0;
const used = new Array(n).fill(false);
while (space > 0) {
let best = -1;
for (let i = 0; i < n; i++)
if (!used[i] && (best === -1 || boxTypes[i][1] > boxTypes[best][1])) best = i;
if (best === -1) break;
used[best] = true;
const take = Math.min(boxTypes[best][0], space);
total += take * boxTypes[best][1];
space -= take;
}
return total;
}2Sort by units, then greedy
O(n log n)Sorting dominates; the greedy pass is linear.O(1)Sorts in place (ignoring the sort's internal stack).Sort the box types by units per box in decreasing order once, then load greedily from the front until the truck is full.
- Sort
boxTypesbyunitsPerBoxdescending. - For each type:
take = min(count, space); addtake * units; reduce space; stop when space is 0.
class Solution {
public int maximumUnits(int[][] boxTypes, int truckSize) {
Arrays.sort(boxTypes, (a, b) -> b[1] - a[1]);
int space = truckSize, total = 0;
for (int[] t : boxTypes) {
if (space == 0) break;
int take = Math.min(t[0], space);
total += take * t[1];
space -= take;
}
return total;
}
}class Solution:
def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
boxTypes.sort(key=lambda t: -t[1])
space, total = truckSize, 0
for cnt, units in boxTypes:
if space == 0:
break
take = min(cnt, space)
total += take * units
space -= take
return totalclass Solution {
public:
int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
sort(boxTypes.begin(), boxTypes.end(), [](const vector<int>& a, const vector<int>& b) { return a[1] > b[1]; });
int space = truckSize, total = 0;
for (auto& t : boxTypes) {
if (space == 0) break;
int take = min(t[0], space);
total += take * t[1];
space -= take;
}
return total;
}
};function maximumUnits(boxTypes, truckSize) {
boxTypes.sort((a, b) => b[1] - a[1]);
let space = truckSize, total = 0;
for (const t of boxTypes) {
if (space === 0) break;
const take = Math.min(t[0], space);
total += take * t[1];
space -= take;
}
return total;
}3Optimal (bucket boxes by units)
O(n + U)One pass to fill buckets and one pass over U = 1000 unit values.O(U)The bucket array of size U + 1.Units per box are at most 1000, so add up the number of boxes for every units value in an array of size 1001. Then walk the units values from 1000 down to 1, loading boxes greedily. No comparison sort is needed.
count[u]+= numberOfBoxes for every type with units u.- For u from 1000 down to 1:
take = min(count[u], space); addtake * u; reduce space; stop at 0.
class Solution {
public int maximumUnits(int[][] boxTypes, int truckSize) {
int[] count = new int[1001];
for (int[] t : boxTypes) count[t[1]] += t[0];
int space = truckSize, total = 0;
for (int u = 1000; u >= 1 && space > 0; u--) {
int take = Math.min(count[u], space);
total += take * u;
space -= take;
}
return total;
}
}class Solution:
def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
count = [0] * 1001
for cnt, units in boxTypes:
count[units] += cnt
space, total = truckSize, 0
for u in range(1000, 0, -1):
if space == 0:
break
take = min(count[u], space)
total += take * u
space -= take
return totalclass Solution {
public:
int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
vector<int> count(1001, 0);
for (auto& t : boxTypes) count[t[1]] += t[0];
int space = truckSize, total = 0;
for (int u = 1000; u >= 1 && space > 0; u--) {
int take = min(count[u], space);
total += take * u;
space -= take;
}
return total;
}
};function maximumUnits(boxTypes, truckSize) {
const count = new Array(1001).fill(0);
for (const t of boxTypes) count[t[1]] += t[0];
let space = truckSize, total = 0;
for (let u = 1000; u >= 1 && space > 0; u--) {
const take = Math.min(count[u], space);
total += take * u;
space -= take;
}
return total;
}Edge cases to test
- Truck capacity larger than the total number of boxes
- Truck fills up in the middle of a box type
- Several types with the same units per box
Hints
Hint 1
Every box takes one slot, so a slot is always best used by the box with the most units.
Hint 2
Process box types from most to fewest units per box, taking as many boxes as still fit.
Hint 3
Units per box are at most 1000, so you can bucket the boxes by units instead of sorting.
FAQ
What is the best time complexity for Maximum Units on a Truck?
Optimal (bucket boxes by units) runs in O(n + U) time and O(U) extra space. One pass to fill buckets and one pass over U = 1000 unit values.
Which pattern does Maximum Units on a Truck use?
It is a arrays & hashing problem that uses the greedy pattern. Other problems with the same pattern: Integer to Roman, Jump Game II, Jump Game.
Is there a brute force solution for Maximum Units on a Truck?
Yes. Brute force (repeatedly pick the best remaining type) takes O(n²) time and O(n) space. While the truck has room, scan all box types for the one with the most units per box that still has boxes, load as many of it as fit, and mark it used.
Which edge cases should I test for Maximum Units on a Truck?
Truck capacity larger than the total number of boxes; Truck fills up in the middle of a box type; Several types with the same units per box.