LeetCode Problem 1710

Difficulty: 🟢 Easy
Topics: Array, Greedy, Sorting

Solution

LeetCode 1710 - Maximum Units on a Truck

Problem Understanding

The problem gives us several types of boxes, where each box type contains two values:

• The number of boxes available for that type
• The number of units inside each box of that type

We also have a truck that can carry at most truckSize boxes total, regardless of type.

Our goal is to maximize the total number of units loaded onto the truck.

In other words, every box occupies exactly one slot on the truck, but different box types contribute different numbers of units. Since the truck has limited capacity, we want to prioritize boxes that give us the most units per box.

For example, if one box type contains 10 units per box and another contains only 1 unit per box, it is usually better to load the 10-unit boxes first because they provide more value for the same truck space.

The input boxTypes is a 2D array where:

• boxTypes[i][0] is the number of boxes of type i
• boxTypes[i][1] is the units per box for type i

The expected output is a single integer representing the maximum total units that can fit on the truck.

The constraints are important:

• There can be up to 1000 box types
• Each type can contain up to 1000 boxes
• truckSize can be as large as 10^6

These constraints suggest that an exponential or combinatorial solution would be far too slow. We need an efficient strategy.

There are several edge cases worth considering:

• The truck may become full before processing all box types.
• The truck may be large enough to take every available box.
• Multiple box types may have the same units per box.
• A box type may contain more boxes than the remaining truck capacity.
• There is always at least one box type and the truck size is always positive, so we do not need to handle empty input arrays.

Approaches

Brute Force Approach

A brute-force solution would try all possible ways of selecting boxes from different types and determine which combination gives the maximum total units.

Conceptually, this resembles a knapsack-style search. For each box type, we could decide how many boxes to take, from zero up to the available count, while keeping track of the remaining truck capacity.

This approach is guaranteed to find the optimal answer because it explores every valid combination.

However, the number of possible combinations grows extremely quickly. Even with relatively small inputs, the search space becomes enormous. Since truckSize can reach one million, exhaustive exploration is completely impractical.

Therefore, we need a more efficient observation.

Optimal Greedy Approach

The key insight is that every box occupies exactly one unit of truck space.

That means the only thing that matters is how many units we gain per box slot.

If we always choose the available box type with the highest units per box first, we maximize the value gained for each truck position.

This is a classic greedy strategy.

The algorithm works as follows:

1. Sort box types by units per box in descending order.
2. Take as many boxes as possible from the most valuable type.
3. Move to the next most valuable type.
4. Continue until the truck becomes full.

This works because choosing a lower-value box before a higher-value box can never improve the total units.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Tries every possible combination of box selections
Optimal	O(n log n)	O(1) or O(log n)	Sorts by units per box and greedily fills truck

Algorithm Walkthrough

1. Sort the boxTypes array in descending order based on numberOfUnitsPerBox.

This ensures that the most valuable boxes are processed first. Since each box consumes the same amount of truck capacity, maximizing units per box is always the best immediate choice. 2. Initialize a variable total_units to 0.

This variable will accumulate the total number of units loaded onto the truck. 3. Iterate through each box type in sorted order.

For every type, determine how many boxes can actually fit into the remaining truck capacity. 4. Compute the number of boxes to take.

The number of boxes we take is:

min(available_boxes, remaining_truck_capacity)

We cannot exceed either the available quantity or the remaining truck space. 5. Add the units contributed by those boxes.

Multiply:

boxes_taken * units_per_box

Add this result to total_units. 6. Reduce the remaining truck capacity.

Subtract the number of boxes taken from truckSize. 7. Stop early if the truck becomes full.

Once truckSize reaches zero, no more boxes can be added. 8. Return total_units.

Why it works

The greedy strategy is correct because every box consumes exactly one unit of truck capacity. Therefore, whenever we choose a box with fewer units instead of a box with more units, we lose potential value without gaining any advantage.

Sorting by units per box guarantees that every truck slot is used as efficiently as possible. Since each decision locally maximizes units gained per box, the overall solution is globally optimal.

Python Solution

from typing import List

class Solution:
    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
        # Sort by units per box in descending order
        boxTypes.sort(key=lambda box: box[1], reverse=True)

        total_units = 0

        for number_of_boxes, units_per_box in boxTypes:
            if truckSize == 0:
                break

            boxes_to_take = min(number_of_boxes, truckSize)

            total_units += boxes_to_take * units_per_box
            truckSize -= boxes_to_take

        return total_units

The implementation begins by sorting the box types according to units per box in descending order. This directly implements the greedy idea of always prioritizing the most valuable boxes first.

The variable total_units stores the cumulative number of units loaded onto the truck.

The loop processes each box type one at a time. For each type, the code determines how many boxes can fit into the remaining truck capacity using min(number_of_boxes, truckSize).

The contribution of the selected boxes is added to total_units, and the truck capacity is reduced accordingly.

The early stopping condition improves efficiency slightly by terminating once the truck is full.

Go Solution

package main

import "sort"

func maximumUnits(boxTypes [][]int, truckSize int) int {
	sort.Slice(boxTypes, func(i, j int) bool {
		return boxTypes[i][1] > boxTypes[j][1]
	})

	totalUnits := 0

	for _, boxType := range boxTypes {
		if truckSize == 0 {
			break
		}

		numberOfBoxes := boxType[0]
		unitsPerBox := boxType[1]

		boxesToTake := numberOfBoxes
		if truckSize < numberOfBoxes {
			boxesToTake = truckSize
		}

		totalUnits += boxesToTake * unitsPerBox
		truckSize -= boxesToTake
	}

	return totalUnits
}

The Go implementation follows the same greedy strategy as the Python version.

The main difference is the use of sort.Slice to sort the 2D slice by units per box in descending order.

Go does not have a built-in min function for integers, so the code manually compares truckSize and numberOfBoxes to determine how many boxes to take.

Integer overflow is not a concern here because the maximum possible answer comfortably fits inside Go's standard integer range under the given constraints.

Worked Examples

Example 1

Input:

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

First, sort by units per box descending:

[[1,3],[2,2],[3,1]]

The array is already sorted.

Step	Box Type	Boxes Taken	Units Added	Remaining Truck Size	Total Units
1	[1,3]	1	1 × 3 = 3	3	3
2	[2,2]	2	2 × 2 = 4	1	7
3	[3,1]	1	1 × 1 = 1	0	8

Final answer:

8

Example 2

Input:

boxTypes = [[5,10],[2,5],[4,7],[3,9]]
truckSize = 10

After sorting:

[[5,10],[3,9],[4,7],[2,5]]

Step	Box Type	Boxes Taken	Units Added	Remaining Truck Size	Total Units
1	[5,10]	5	50	5	50
2	[3,9]	3	27	2	77
3	[4,7]	2	14	0	91

Final answer:

91

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(1) or O(log n)	Depends on sorting implementation details

The algorithm spends most of its time sorting the box types. After sorting, the single traversal through the array is linear.

The extra memory usage is minimal because the sorting is performed in place. Some sorting implementations may use logarithmic stack space internally.

Test Cases

from typing import List

class Solution:
    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
        boxTypes.sort(key=lambda box: box[1], reverse=True)

        total_units = 0

        for number_of_boxes, units_per_box in boxTypes:
            if truckSize == 0:
                break

            boxes_to_take = min(number_of_boxes, truckSize)

            total_units += boxes_to_take * units_per_box
            truckSize -= boxes_to_take

        return total_units

solution = Solution()

assert solution.maximumUnits([[1,3],[2,2],[3,1]], 4) == 8
# Basic example from problem statement

assert solution.maximumUnits([[5,10],[2,5],[4,7],[3,9]], 10) == 91
# Larger mixed example

assert solution.maximumUnits([[1,1]], 1) == 1
# Smallest valid input

assert solution.maximumUnits([[10,5]], 3) == 15
# Truck cannot take all boxes

assert solution.maximumUnits([[2,4],[3,4]], 4) == 16
# Multiple box types with same units per box

assert solution.maximumUnits([[5,10],[5,9]], 10) == 95
# Truck exactly fits all boxes

assert solution.maximumUnits([[1000,1000]], 1000) == 1000000
# Maximum values within constraints

assert solution.maximumUnits([[3,1],[3,2],[3,3]], 2) == 6
# Truck fills before processing all box types

assert solution.maximumUnits([[2,8],[1,9],[4,3]], 1) == 9
# Truck can only take highest value box

assert solution.maximumUnits([[5,4],[2,7]], 20) == 34
# Truck larger than total available boxes

Test Summary

Test	Why
[[1,3],[2,2],[3,1]], 4	Validates the basic greedy strategy
[[5,10],[2,5],[4,7],[3,9]], 10	Tests sorting and partial selection
[[1,1]], 1	Smallest valid input
[[10,5]], 3	Ensures partial box selection works
[[2,4],[3,4]], 4	Handles equal units per box
[[5,10],[5,9]], 10	Exact truck fit
[[1000,1000]], 1000	Stress test with large values
[[3,1],[3,2],[3,3]], 2	Truck fills early
[[2,8],[1,9],[4,3]], 1	Only highest value box should be chosen
[[5,4],[2,7]], 20	Truck larger than total boxes

Edge Cases

Truck Capacity Smaller Than a Single Box Type

A common source of bugs occurs when the truck cannot take all boxes from the current type.

For example:

boxTypes = [[10,5]]
truckSize = 3

A naive implementation might accidentally add all 10 boxes instead of only 3. The solution correctly handles this using:

min(number_of_boxes, truckSize)

This guarantees we never exceed capacity.

Truck Larger Than Total Available Boxes

Another edge case happens when the truck has more capacity than the total number of available boxes.

For example:

boxTypes = [[2,3],[1,5]]
truckSize = 10

The correct behavior is to take every available box and stop naturally when the input is exhausted. The implementation handles this automatically because the loop simply finishes after processing all box types.

Multiple Box Types With Equal Units Per Box

If several box types provide the same units per box, sorting order between them does not matter.

For example:

boxTypes = [[2,4],[3,4]]

Any order produces the same total units because every truck slot contributes equally. The greedy algorithm still works correctly because all equivalent choices yield the same value.

Truck Becomes Full Early

The truck may become full before all box types are processed.

For example:

boxTypes = [[5,10],[5,1]]
truckSize = 2

Once the truck is full after taking two high-value boxes, continuing the loop would be unnecessary. The implementation includes an early termination check:

if truckSize == 0:
    break

This avoids unnecessary computation while maintaining correctness.