Maximum Units on a Truck solution and explanation
IBM
Google
9 more videos on this problem
Leetcode 1710. Maximum Units on a Truck || Code + Explanation + Example || June Daily ChallengeCode with Alisha · 14:31 · 7K views
Maximum Units on a Truck | Leetcode 1710 | Live coding sessionCoding Decoded · 10:02 · 4K views
Leetcode - Maximum Units on a Truck (Python)Timothy H Chang · 4:26 · 3K views
MAXIMUM UNITS ON A TRUCK | LEETCODE 1710 | PYTHON HEAP SOLUTIONCracking FAANG · 10:33 · 2K views
1710. Maximum Units on a Truck (Leetcode Easy)Programming Live with Larry · 5:35 · 1K views
Leetcode 1710. Maximum Units on a Truck | Leetcode Weekly Contest 222INFO DECODER · 6:43 · 1K views
Maximum Units on a Truck | LEETCODE - 1710 | Easy solutionhi-malik · 10:01 · 1K views
Maximum Units on a Truck | LeetCode 1710 | Coders CampCoders Camp · 7:23 · 1K views
Leetcode 1710 Maximum Units on a Truck | 👉🏼 Coding Decoded SDE SheetCoding Decoded · 4:38 · 949 views
Daily Leetcode #822: Jul 01, 2022 - 1710. Maximum Units on a TruckProgramming Live with Larry · 8:25 · 440 views
The problem
You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]:
numberOfBoxesiis the number of boxes of typei.numberOfUnitsPerBoxiis the number of units in each box of the typei.
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 of boxes does not 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: There are: - 1 box of the first type that contains 3 units. - 2 boxes of the second type that contain 2 units each. - 3 boxes of the third type that contain 1 unit each. You can take all the boxes of the first and second types, and one box of the third type. The total number of units will be = (1 * 3) + (2 * 2) + (1 * 1) = 8.
Example 2:
Input: boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10 Output: 91
Constraints:
1 <= boxTypes.length <= 10001 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 10001 <= truckSize <= 106
Approach overview
Problem Overview: You are given different box types where each type contains a number of boxes and a number of units per box. A truck can carry at most truckSize boxes. The goal is to load boxes so the total units on the truck is maximized.
Approach 1: Greedy Approach using Sorting (Time: O(n log n), Space: O(1) or O(n) depending on sorting implementation)
This problem fits the greedy pattern. Each box type has a "value" (units per box). To maximize total units, always load boxes that give the highest units first. Start by sorting the box types in descending order by unitsPerBox using a sorting algorithm. Then iterate through the sorted list and take as many boxes as possible from each type until the truck reaches its capacity.
For each box type, compute boxesTaken = min(numberOfBoxes, remainingTruckCapacity). Multiply that by unitsPerBox and add it to the total. Decrease the remaining capacity and continue. The key insight is that a locally optimal choice (highest units per box first) leads to the global optimum because each box contributes independently to the final total.
This approach is simple and reliable. Sorting dominates the runtime with O(n log n), where n is the number of box types. The rest of the algorithm is a single pass over the array. Space complexity is O(1) if the sort is in-place. The input structure is just an array of box types.
Approach 2: Counting Sort Based Approach (Time: O(n + k), Space: O(k))
The constraints allow an optimization using counting sort. Instead of sorting box types directly, group them by unitsPerBox. Since the maximum units per box is bounded (commonly ≤1000 in the problem constraints), create a frequency structure where each index represents a specific units value.
Iterate through the input and accumulate how many boxes exist for each unitsPerBox value. Then traverse this structure from the highest unit value down to the lowest. At each step, greedily load as many boxes as possible until the truck is full.
This avoids the O(n log n) sorting step. Building the counts takes O(n), and scanning the bucket array takes O(k), where k is the maximum possible units per box. The approach uses O(k) additional space but improves runtime when n is large and the unit range is small.
Recommended for interviews: The greedy sorting solution is what most interviewers expect first. It clearly demonstrates recognition of the greedy pattern and is easy to implement under time pressure. The counting sort optimization shows deeper understanding of constraints and can improve performance when the unit range is limited.
Approach 1: Greedy Approach using Sorting
This approach involves sorting the box types by the number of units per box in descending order. Once sorted, the boxes are loaded onto the truck with the highest units per box first, maximizing the number of units on the truck until it reaches its capacity.
def maximumUnits(boxTypes, truckSize):
boxTypes.sort(key=lambda x: -x[1])
total_units = 0
for numberOfBoxes, unitsPerBox in boxTypes:
boxes_to_take = min(numberOfBoxes, truckSize)
total_units += boxes_to_take * unitsPerBox
truckSize -= boxes_to_take
if truckSize == 0:
break
return total_unitsimport java.util.Arrays;
class Solution {
public int maximumUnits(int[][] boxTypes, int truckSize) {
Arrays.sort(boxTypes, (a, b) -> b[1] - a[1]);
int totalUnits = 0;
for (int[] box : boxTypes) {
int boxesToTake = Math.min(box[0], truckSize);
totalUnits += boxesToTake * box[1];
truckSize -= boxesToTake;
if (truckSize == 0) break;
}
return totalUnits;
}
}#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
sort(boxTypes.begin(), boxTypes.end(), [](const vector<int>& a, const vector<int>& b) {
return b[1] > a[1];
});
int totalUnits = 0;
for (const auto& box : boxTypes) {
int boxesToTake = min(box[0], truckSize);
totalUnits += boxesToTake * box[1];
truckSize -= boxesToTake;
if (truckSize == 0) break;
}
return totalUnits;
}
};function maximumUnits(boxTypes, truckSize) {
boxTypes.sort((a, b) => b[1] - a[1]);
let totalUnits = 0;
for (const [numberOfBoxes, unitsPerBox] of boxTypes) {
const boxesToTake = Math.min(numberOfBoxes, truckSize);
totalUnits += boxesToTake * unitsPerBox;
truckSize -= boxesToTake;
if (truckSize === 0) break;
}
return totalUnits;
}#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b) {
int* boxA = *(int**)a;
int* boxB = *(int**)b;
return boxB[1] - boxA[1];
}
int maximumUnits(int** boxTypes, int boxTypesSize, int* boxTypesColSize, int truckSize) {
qsort(boxTypes, boxTypesSize, sizeof(int*), compare);
int totalUnits = 0;
for (int i = 0; i < boxTypesSize; ++i) {
int boxesToTake = fmin(boxTypes[i][0], truckSize);
totalUnits += boxesToTake * boxTypes[i][1];
truckSize -= boxesToTake;
if (truckSize == 0) {
break;
}
}
return totalUnits;
}using System;
public class Solution {
public int MaximumUnits(int[][] boxTypes, int truckSize) {
Array.Sort(boxTypes, (a, b) => b[1] - a[1]);
int totalUnits = 0;
foreach (var box in boxTypes) {
int boxesToTake = Math.Min(box[0], truckSize);
totalUnits += boxesToTake * box[1];
truckSize -= boxesToTake;
if (truckSize == 0) break;
}
return totalUnits;
}
}Python solution leverages sorting using lambda to order box types by units and iteratively fill the truck to maximize units.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1).
Approach 2: Counting Sort Based Approach
Instead of sorting by each unit's count, employ counting sort principles to store the total units in an array where the index represents the units per box. This could potentially be faster for large inputs with many boxes and limited unit types.
def maximumUnits(boxTypes, truckSize):
MAX_UNITS = 1000
count = [0] * (MAX_UNITS + 1)
for numberOfBoxes, unitsPerBox in boxTypes:
count[unitsPerBox] += numberOfBoxes
total_units = 0
for units in range(MAX_UNITS, 0, -1):
if count[units] > 0:
boxes_to_take = min(truckSize, count[units])
total_units += boxes_to_take * units
truckSize -= boxes_to_take
if truckSize == 0:
break
return total_unitspublic class Solution {
private static final int MAX_UNITS = 1000;
public int maximumUnits(int[][] boxTypes, int truckSize) {
int[] count = new int[MAX_UNITS + 1];
for (int[] box : boxTypes) {
count[box[1]] += box[0];
}
int totalUnits = 0;
for (int i = MAX_UNITS; i > 0 && truckSize > 0; --i) {
if (count[i] > 0) {
int boxesToTake = Math.min(truckSize, count[i]);
totalUnits += boxesToTake * i;
truckSize -= boxesToTake;
}
}
return totalUnits;
}
}#include <vector>
using namespace std;
#define MAX_UNITS 1000
class Solution {
public:
int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
vector<int> count(MAX_UNITS + 1, 0);
for (const auto& box : boxTypes) {
count[box[1]] += box[0];
}
int totalUnits = 0;
for (int i = MAX_UNITS; i > 0 && truckSize > 0; --i) {
if (count[i] > 0) {
int boxesToTake = min(truckSize, count[i]);
totalUnits += boxesToTake * i;
truckSize -= boxesToTake;
}
}
return totalUnits;
}
};function maximumUnits(boxTypes, truckSize) {
const MAX_UNITS = 1000;
const count = Array(MAX_UNITS + 1).fill(0);
for (const [numberOfBoxes, unitsPerBox] of boxTypes) {
count[unitsPerBox] += numberOfBoxes;
}
let totalUnits = 0;
for (let i = MAX_UNITS; i > 0 && truckSize > 0; --i) {
if (count[i] > 0) {
const boxesToTake = Math.min(truckSize, count[i]);
totalUnits += boxesToTake * i;
truckSize -= boxesToTake;
}
}
return totalUnits;
}#include <stdio.h>
#include <stdlib.h>
#define MAX_UNITS 1000
int maximumUnits(int** boxTypes, int boxTypesSize, int* boxTypesColSize, int truckSize) {
int count[MAX_UNITS + 1] = {0};
for (int i = 0; i < boxTypesSize; ++i) {
count[boxTypes[i][1]] += boxTypes[i][0];
}
int totalUnits = 0;
for (int i = MAX_UNITS; i > 0 && truckSize > 0; --i) {
if (count[i] > 0) {
int boxesToTake = truckSize < count[i] ? truckSize : count[i];
totalUnits += boxesToTake * i;
truckSize -= boxesToTake;
}
}
return totalUnits;
}public class Solution {
private const int MAX_UNITS = 1000;
public int MaximumUnits(int[][] boxTypes, int truckSize) {
int[] count = new int[MAX_UNITS + 1];
foreach (var box in boxTypes) {
count[box[1]] += box[0];
}
int totalUnits = 0;
for (int i = MAX_UNITS; i > 0 && truckSize > 0; --i) {
if (count[i] > 0) {
int boxesToTake = Math.Min(truckSize, count[i]);
totalUnits += boxesToTake * i;
truckSize -= boxesToTake;
}
}
return totalUnits;
}
}Python solution utilizes a counting array approach where units are prioritized by their count indices, providing quick access to maximum unit decisions.
Time Complexity: O(n + M).
Space Complexity: O(M).
Approach 3: Greedy + Sorting
According to the problem, we should choose as many units as possible. Therefore, we first sort boxTypes in descending order of the number of units.
Then we traverse boxTypes from front to back, choose up to truckSize boxes, and accumulate the number of units.
The time complexity is O(n times log n), where n is the length of the two-dimensional array boxTypes.
export function maximumUnits(boxTypes: number[][], truckSize: number): number {
boxTypes.sort(([_, a], [__, b]) => b - a);
let ans = 0;
for (const [count, size] of boxTypes) {
ans += Math.min(truckSize, count) * size;
truckSize -= count;
if (truckSize < 0) break;
}
return ans;
}func maximumUnits(boxTypes [][]int, truckSize int) (ans int) {
sort.Slice(boxTypes, func(i, j int) bool { return boxTypes[i][1] > boxTypes[j][1] })
for _, e := range boxTypes {
a, b := e[0], e[1]
ans += b * min(truckSize, a)
truckSize -= a
if truckSize <= 0 {
break
}
}
return
}impl Solution {
pub fn maximum_units(mut box_types: Vec<Vec<i32>>, truck_size: i32) -> i32 {
box_types.sort_by(|a, b| b[1].cmp(&a[1]));
let mut sum = 0;
let mut ans = 0;
for box_type in box_types.iter() {
if sum + box_type[0] < truck_size {
sum += box_type[0];
ans += box_type[0] * box_type[1];
} else {
ans += (truck_size - sum) * box_type[1];
break;
}
}
ans
}
}Approach 4: Counting Sort
We can also use the idea of counting sort, create an array cnt of length 1001, where cnt[b] represents the number of boxes with b units.
Then starting from the box with the maximum number of units, choose up to truckSize boxes, and accumulate the number of units.
The time complexity is O(M), where M is the maximum number of units. In this problem, M=1000.
function maximumUnits(boxTypes: number[][], truckSize: number): number {
boxTypes.sort(([_, a], [__, b]) => b - a);
let ans = 0;
for (const [count, size] of boxTypes) {
ans += Math.min(truckSize, count) * size;
truckSize -= count;
if (truckSize < 0) {
break;
}
}
return ans;
}func maximumUnits(boxTypes [][]int, truckSize int) (ans int) {
cnt := [1001]int{}
for _, e := range boxTypes {
a, b := e[0], e[1]
cnt[b] += a
}
for b := 1000; b > 0 && truckSize > 0; b-- {
a := cnt[b]
if a > 0 {
ans += b * min(truckSize, a)
truckSize -= a
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach using Sorting | Time Complexity: O(n log n) due to sorting. |
| Counting Sort Based Approach | Time Complexity: O(n + M). |
| Greedy + Sorting | – |
| Counting Sort | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting | O(n log n) | O(1) to O(n) | General solution. Simple and commonly expected in interviews. |
| Counting Sort Optimization | O(n + k) | O(k) | When units per box have a small bounded range and you want linear time. |
Frequently asked questions
Is Maximum Units on a Truck easy or hard?
Maximum Units on a Truck is classified as an Easy problem on LeetCode. The key idea is recognizing the greedy strategy: always pick the box type with the highest units per box first. Once that insight is clear, the implementation is straightforward.
How to solve Maximum Units on a Truck in O(n)?
Use a counting sort style technique. Instead of sorting box types, count how many boxes exist for each units-per-box value. Then iterate from the highest unit value downward and greedily load boxes. This runs in O(n + k) time where k is the maximum possible units per box.
What is the best approach for Maximum Units on a Truck?
The greedy approach with sorting is the most common and reliable solution. Sort box types by units per box in descending order and always pick the highest-value boxes first until the truck reaches capacity. This strategy works because each box contributes independently to the final total. The time complexity is O(n log n).
What data structure is used in Maximum Units on a Truck?
The main structure is an array of box types, where each element stores the number of boxes and units per box. The greedy solution relies on sorting this array, while the optimized version uses a counting array (bucket structure) indexed by units per box.
What is the time complexity of Maximum Units on a Truck?
The standard greedy solution runs in O(n log n) time due to sorting the box types by units per box. After sorting, a single linear pass selects boxes until the truck is full. An optimized counting sort approach can reduce the runtime to O(n + k), where k is the maximum units per box.
Maximum Units on a Truck Python or Java solution approach?
In both Python and Java, the typical solution sorts the box types by units per box in descending order using built-in sorting functions. After sorting, iterate through the list, take the minimum of available boxes and remaining truck capacity, and accumulate the total units.
Is Maximum Units on a Truck asked at Google, Amazon, or Meta?
This problem represents a classic greedy optimization pattern and appears frequently in technical interview preparation lists. Variations of greedy selection and resource allocation problems are common at companies like Amazon, Google, and Meta, making it a useful practice question.