EasyArrayGreedySortingUpdated Sep 2026

1710. Maximum Units on a Truck

Asked at JPMorgan

Difficulty

Easy

Time

O(n log n)

Space

O(1)

Pattern

Array

Companies

1

Problem

You have a truck that can carry at most truckSize boxes. You are given boxTypes, a list of box types. Each entry is a pair [numberOfBoxes, unitsPerBox]: how many boxes of that type exist, and how many units each of those boxes contains.

All boxes take the same amount of space on the truck — one box is one slot, no matter its type. You may pick any mix of boxes, as long as the total number of boxes you load is at most truckSize.

Return the maximum total number of units you can load onto the truck.

Pick the best boxes for the slots

boxTypescountunitstype 0type 1type 21322311 box of 3 units, 2 boxes of 2 units, 3 boxes of 1unittruck (4 slots)32210123Total units = 3 + 2 + 2 + 1 = 8
The truck has 4 slots, and each slot should hold the box with the most units still available.

Constraints

  • ●1 <= boxTypes.length <= 1000
  • ●1 <= numberOfBoxes, unitsPerBox <= 1000
  • ●1 <= truckSize <= 10^6

Examples

Example 1
InputboxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
Output8
WhyTake the 1 box worth 3 units and both boxes worth 2 units (that is 3 boxes), then 1 of the 3 boxes worth 1 unit. Total = 3 + 2 + 2 + 1 = 8. Every slot is filled with the best box still available.
Example 2
InputboxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
Output91
WhySort by units per box: 10, 9, 7, 5. Take 5 boxes of 10 units (50), 3 boxes of 9 units (27), then 2 of the 4 boxes of 7 units (14). Total = 50 + 27 + 14 = 91, and the truck is full with 10 boxes.

Asked At

1 companies
CompanyDifficulty
JPMorganEasyView all JPMorgan questions →

How to Think About It

1

Every box occupies one slot regardless of type, so each slot should hold the box with the most units available.

2

Sort box types by units per box, descending.

3

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.

4

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.

5

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.

Sort by units, then fill greedily

sorted by units[1,3][2,2][3,1]012iStart with the richest box type: 1 box of 3 unitssorted by units[1,3][2,2][3,1]012iCapacity left = 3, so take both boxes of 2 unitssorted by units[1,3][2,2][3,1]012iCapacity left = 1, so take only 1 of the 3 boxes of 1unittake = min(count, truckSize)total += take * unitstruckSize -= take
After sorting, take as many boxes as fit from each type until the truck is full.
ComplexityTime O(n log n)Space O(1)The cost is the sort by units per box; the greedy pass afterwards touches each type once.

What Trips People Up in Real Interviews

1

Sorting by the number of boxes instead of units per box.

2

Taking every box of a type even when the truck has less room left.

3

Treating it like a 0/1 knapsack. Every box has the same size, so greedy is optimal.

4

Not stopping once the truck is full — harmless, but it shows you did not think about the loop exit.

Solution Code

O(n log n) time
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 total

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(n log n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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.