#1710

Easy

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Maximum Units on a Truck

Maximize total units loaded on a truck by choosing boxes greedily based on highest units per box within truck capacity limits.

array greedy sorting

Problem Statement

You are given a 2D array boxTypes where boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]. Each entry represents a type of box, the number available, and the units contained. Your goal is to load boxes onto a truck to maximize total units.

You also have an integer truckSize indicating the maximum number of boxes that can fit on the truck. You may select any combination of boxes without exceeding this limit. Return the maximum total units that the truck can carry.

Examples

Example 1

Input: boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4

Output: 8

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

Example details omitted.

Constraints

1 <= boxTypes.length <= 1000
1 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000
1 <= truckSize <= 106

Solution Approach

Sort Box Types by Units

Sort the boxTypes array in descending order based on numberOfUnitsPerBoxi. This ensures the greedy choice—always picking the box with the most units per box—is straightforward and aligns with the invariant for maximizing units.

Iterative Loading

Traverse the sorted array and add boxes to the truck one type at a time. For each type, add either all available boxes or just enough to reach truckSize, whichever is smaller. Update the total units accumulated during this process.

Early Termination

Stop adding boxes once the truckSize limit is reached. This prevents overfilling and confirms the greedy invariant that no further units can be gained beyond this point.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) due to sorting, where n is the number of box types. Space complexity is O(1) extra space if sorting in place, otherwise O(n). Iteration over box types is linear, O(n).

What Interviewers Usually Probe

Mentions prioritizing boxes with higher units per box.
Asks how to handle remaining truck capacity after partial selection of a box type.
Looks for proof that greedy selection guarantees maximum units.

Common Pitfalls or Variants

Common pitfalls

Failing to sort by units per box, leading to suboptimal total units.
Ignoring the truckSize limit when adding boxes, which breaks constraints.
Adding boxes of a lower-unit type before exhausting higher-unit types.

Follow-up variants

Maximize total units with multiple trucks each with different capacities.
Boxes have weights and units; maximize units without exceeding truck weight limit.
Box types may have expiration or priority constraints affecting loading order.

FAQ

What is the core greedy strategy in Maximum Units on a Truck?

Always select boxes with the highest units per box first until the truck is full. This guarantees maximal total units.

Can I use dynamic programming instead of greedy for this problem?

Dynamic programming is unnecessary and less efficient; the greedy approach with sorting suffices to maximize units.

How do I handle remaining capacity if the next box type has more boxes than space left?

Take only as many boxes as fit in the remaining truck capacity and stop when full.

Does the order of boxTypes in the input affect the solution?

No, sorting by units per box ensures the greedy selection works regardless of initial order.

What pattern does this problem illustrate for interviews?

It demonstrates 'Greedy choice plus invariant validation', highlighting decision-making that always maximizes immediate gain while maintaining constraints.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

class Solution:
    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
        ans = 0
        for a, b in sorted(boxTypes, key=lambda x: -x[1]):
            ans += b * min(truckSize, a)
            truckSize -= a
            if truckSize <= 0:
                break
        return ans

Solution 2: 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.

1

2

3

4

5

6

7

8

9

class Solution:
    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
        ans = 0
        for a, b in sorted(boxTypes, key=lambda x: -x[1]):
            ans += b * min(truckSize, a)
            truckSize -= a
            if truckSize <= 0:
                break
        return ans

Continue Practicing

#1727 largest submatrix with rearrangements #1686 stone game vi #1665 minimum initial energy to finish tasks