Maximum Units on a Truck

Easy

#1567Time: O(N log N), where N is the number of box types (`boxTypes.length`). The sorting step dominates the time complexity. The subsequent loop runs at most N times.Space: O(log N) or O(N), depending on the implementation of the sorting algorithm used. In Java, `Arrays.sort` for objects uses TimSort, which requires O(N) space in the worst case.3 companies

Patterns

Greedy

Algorithms

Sorting

Data structures

Array

Companies

IBM J.P. Morgan Arista Networks

Prompt

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

numberOfBoxes_i is the number of boxes of type i.
numberOfUnitsPerBox_iis 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 <= numberOfBoxes_i, numberOfUnitsPerBox_i <= 1000
1 <= truckSize <= 10⁶

Approaches

2 approaches with complexity analysis and trade-offs.

This approach is based on the greedy principle that to maximize the total units, we should always prioritize loading the boxes that offer the most units. By sorting the box types in descending order based on the number of units per box, we can iteratively fill the truck with the most valuable boxes first.

Algorithm

Sort the boxTypes 2D array in descending order based on the second element (units per box).
Initialize a variable totalUnits to 0.
Iterate through the sorted boxTypes array.
For each boxType, get the numberOfBoxes and unitsPerBox.
Calculate the number of boxes to load for the current type: boxesToTake = min(numberOfBoxes, remaining truckSize).
Add the units to the total: totalUnits += boxesToTake * unitsPerBox.
Update the remaining truck size: truckSize -= boxesToTake.
If truckSize becomes 0, break the loop.
Return totalUnits.

Walkthrough

The core idea is to be greedy. We want to load the boxes that give us the maximum number of units.

First, we sort the boxTypes array. The sorting criterion is the number of units per box (boxTypes[i][1]) in descending order. This ensures that we consider the most "unit-dense" boxes first.

After sorting, we iterate through the sorted list of box types.

In each iteration, we check the remaining capacity of the truck (truckSize).

We take as many boxes of the current type as we can. The number of boxes to take is the minimum of the available boxes of that type and the remaining truck capacity.

We add the units from the loaded boxes to our total count and decrease the truckSize by the number of boxes we loaded.

We continue this process until we have either considered all box types or the truck is full (truckSize is 0).

Finally, we return the total accumulated units.

1import java.util.Arrays;2import java.util.Comparator;3 4class Solution {5    public int maximumUnits(int[][] boxTypes, int truckSize) {6        // Sort the boxTypes array in descending order of units per box.7        Arrays.sort(boxTypes, (a, b) -> b[1] - a[1]);8 9        int totalUnits = 0;10        for (int[] boxType : boxTypes) {11            int numberOfBoxes = boxType[0];12            int unitsPerBox = boxType[1];13 14            // Determine how many boxes of this type to take.15            int boxesToTake = Math.min(numberOfBoxes, truckSize);16 17            totalUnits += boxesToTake * unitsPerBox;18            truckSize -= boxesToTake;19 20            // If the truck is full, we can stop.21            if (truckSize == 0) {22                break;23            }24        }25        return totalUnits;26    }27}

Complexity

Time

O(N log N), where N is the number of box types (`boxTypes.length`). The sorting step dominates the time complexity. The subsequent loop runs at most N times.

Space

O(log N) or O(N), depending on the implementation of the sorting algorithm used. In Java, `Arrays.sort` for objects uses TimSort, which requires O(N) space in the worst case.

Trade-offs

Pros

Relatively simple and intuitive to implement.
Correctly solves the problem by following a greedy strategy.

Cons

The O(N log N) time complexity from sorting is not the most optimal solution possible for this problem's constraints.

This approach improves upon the sorting method by recognizing that the number of units per box is constrained to a small range (1 to 1000). Instead of a general-purpose comparison sort, we can use a more efficient, non-comparison-based sorting technique like Counting Sort (or Bucket Sort). This allows us to group boxes by their unit count and process them in descending order of units without an O(N log N) sorting overhead.

Algorithm

Create an integer array bucket of size 1001, initialized to zeros.
Iterate through the boxTypes array. For each [numberOfBoxes, unitsPerBox], add numberOfBoxes to bucket[unitsPerBox].
Initialize totalUnits to 0.
Iterate from i = 1000 down to 1.
If bucket[i] is greater than 0: a. Calculate the number of boxes to load: boxesToTake = min(bucket[i], remaining truckSize). b. Add the units to the total: totalUnits += boxesToTake * i. c. Update the remaining truck size: truckSize -= boxesToTake. d. If truckSize becomes 0, break the loop.
Return totalUnits.

Walkthrough

The key observation is that numberOfUnitsPerBox is between 1 and 1000. This limited range allows for a linear time sorting algorithm.

We create an array, let's call it bucket, of size 1001. bucket[i] will store the total count of boxes that contain i units each.

We iterate through the input boxTypes. For each [numberOfBoxes, unitsPerBox], we update our bucket: bucket[unitsPerBox] += numberOfBoxes. After this step, bucket effectively stores all boxes, grouped and counted by their unit value.

Next, we iterate through our bucket array, but in reverse order (from 1000 down to 1), because we want to load the boxes with the most units first.

For each unit value i, we check if bucket[i] has any boxes.

If it does, we determine how many boxes to take: boxesToTake = Math.min(truckSize, bucket[i]).

We update our totalUnits by boxesToTake * i and decrease truckSize by boxesToTake.

If truckSize reaches 0, we have filled the truck, and we can stop and return the result.

This method avoids the O(N log N) sort and achieves a linear time complexity.

1class Solution {2    public int maximumUnits(int[][] boxTypes, int truckSize) {3        // Create a bucket array to count boxes for each unit value.4        // The maximum number of units per box is 1000.5        int[] bucket = new int[1001];6        for (int[] boxType : boxTypes) {7            int numberOfBoxes = boxType[0];8            int unitsPerBox = boxType[1];9            bucket[unitsPerBox] += numberOfBoxes;10        }11 12        int totalUnits = 0;13        // Iterate from the highest unit count down to the lowest.14        for (int units = 1000; units >= 1; units--) {15            // If there are boxes with this unit count.16            if (bucket[units] > 0) {17                // Determine how many boxes of this type to take.18                int boxesToTake = Math.min(bucket[units], truckSize);19                20                totalUnits += boxesToTake * units;21                truckSize -= boxesToTake;22 23                // If the truck is full, we can stop.24                if (truckSize == 0) {25                    break;26                }27            }28        }29        return totalUnits;30    }31}

Complexity

Time

O(N + M), where N is the number of box types and M is the maximum possible units per box (1001). The first loop takes O(N) to populate the buckets. The second loop takes O(M) to iterate through the buckets. Since M is a constant, the overall complexity is linear, O(N).

Space

O(M), for the bucket array, where M is the maximum possible units per box (1001). Since M is a constant, this is considered O(1) constant space.

Trade-offs

Pros

Highly efficient with linear time complexity, which is better than the sorting approach.
Constant space complexity as the size of the bucket array is fixed.

Cons

This approach is only efficient because the range of unitsPerBox is small and known. If the range were very large, this method would become impractical due to high space requirements.

Solutions

Solution

1class Solution {2public3  int maximumUnits(int[][] boxTypes, int truckSize) {4    Arrays.sort(boxTypes, (a, b)->b[1] - a[1]);5    int ans = 0;6    for (var e : boxTypes) {7      int a = e[0], b = e[1];8      ans += b * Math.min(truckSize, a);9      truckSize -= a;10      if (truckSize <= 0) {11        break;12      }13    }14    return ans;15  }16}

1class Solution {2public:3  int maximumUnits(vector<vector<int>> &boxTypes, int truckSize) {4    sort(boxTypes.begin(), boxTypes.end(),5         [](auto &a, auto &b) { return a[1] > b[1]; });6    int ans = 0;7    for (auto &e : boxTypes) {8      int a = e[0], b = e[1];9      ans += b * min(truckSize, a);10      truckSize -= a;11      if (truckSize <= 0)12        break;13    }14    return ans;15  }16};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem