Maximum Units on a Truck

Difficulty: Easy | Acceptance: 74.80% | Paid: No Topics: Array, Greedy, Sorting

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 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.

• Examples
• Constraints
• Greedy with Sorting
• Counting Sort (Bucket Sort)

Examples

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 + 2 + 2 + 3 = 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 <= 10^6

Greedy with Sorting

Intuition To maximize the total units, we should prioritize boxes that offer the most units per box. By sorting the box types in descending order based on their units per box, we can greedily fill the truck with the most valuable boxes first.

Steps

• Sort the boxTypes array based on the number of units per box in descending order.
• Iterate through the sorted array.
• For each box type, take as many boxes as possible (either all available boxes or as many as the remaining truck size allows).
• Add the total units from the taken boxes to the result and decrement the remaining truck size.
• Stop if the truck is full.

class Solution:
    def maximumUnits(self, boxTypes: list[list[int]], truckSize: int) -> int:
        # Sort by units per box in descending order
        boxTypes.sort(key=lambda x: x[1], reverse=True)
        
        total_units = 0
        
        for boxes, units in boxTypes:
            if truckSize >= boxes:
                total_units += boxes * units
                truckSize -= boxes
            else:
                total_units += truckSize * units
                break
                
        return total_units

Complexity

• Time: O(N log N) due to sorting, where N is the number of box types.
• Space: O(1) or O(N) depending on the sorting algorithm’s implementation.
• Notes: Sorting is the most straightforward approach but has a logarithmic time factor.

Counting Sort (Bucket Sort)

Intuition The constraints state that the number of units per box is at most 1000. Instead of sorting, we can use an array (bucket sort) where the index represents the number of units and the value represents the total number of boxes available with that unit count. This allows us to iterate from the highest units downwards in linear time relative to the fixed range.

Steps

• Initialize an array count of size 1001 (since units are between 1 and 1000) with zeros.
• Iterate through boxTypes and accumulate the number of boxes for each unit value in the count array.
• Iterate through the count array from index 1000 down to 1.
• For each unit count, take as many boxes as possible, add to the total, and update the remaining truck size.
• Stop if the truck is full.

class Solution:
    def maximumUnits(self, boxTypes: list[list[int]], truckSize: int) -> int:
        # Bucket array to store count of boxes for each unit value
        # Max units per box is 1000
        unit_counts = [0] * 1001
        
        for boxes, units in boxTypes:
            unit_counts[units] += boxes
        
        total_units = 0
        
        # Iterate from highest units to lowest
        for units in range(1000, 0, -1):
            if truckSize == 0:
                break
            
            available_boxes = unit_counts[units]
            
            if available_boxes > 0:
                take = min(truckSize, available_boxes)
                total_units += take * units
                truckSize -= take
                
        return total_units

Complexity

• Time: O(N + K), where N is the number of box types and K is the maximum units per box (1000). Since K is constant, this is effectively O(N).
• Space: O(K) for the counting array, which is constant space (1001 integers).
• Notes: This approach is more efficient than sorting when the range of values (units per box) is small and fixed.