Skip to main content
Talentd

Maximum Units on a Truck - Solution & Explanation

EasyArrayGreedySorting18 min readAsked at: Amazon, Microsoft, Meta +6
Practice this problem

Problem Statement

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

  • numberOfBoxesi is the number of boxes of type i.
  • numberOfUnitsPerBoxi is the number of units in each box of the 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 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 <= 1000
  • 1 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000
  • 1 <= 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.

This solution sorts the boxTypes array based on the units per box in descending order. Then, it iterates through the sorted array, adding as many boxes as possible from each type to the truck until the truck's capacity is reached. The function returns the total units accumulated.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) extra space, as we sort in place.

Try this approach in the editor →

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.

This approach uses a counting array where the index represents units per box to aggregate total boxes available. The truck is filled according to the highest units available in the count array.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + M) where M = 1000 is a constant.
Space Complexity: O(M) for the counting array.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach using Sorting

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) extra space, as we sort in place.

Counting Sort Based Approach

Time Complexity: O(n + M) where M = 1000 is a constant.
Space Complexity: O(M) for the counting array.

Greedy + Sorting—
Counting Sort—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with SortingO(n log n)O(1) to O(n)General solution. Simple and commonly expected in interviews.
Counting Sort OptimizationO(n + k)O(k)When units per box have a small bounded range and you want linear time.

Video Solution

Leetcode 1710. Maximum Units on a Truck || Code + Explanation + Example || June Daily Challenge • Code with Alisha • 7,124 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Maximum Units on a Truck with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Bags With Full Capacity of Rocks