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 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 <= 10001 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 10001 <= truckSize <= 106This approach involves sorting the box types by the number of units per box in descending order. Once sorted, the boxes are loaded onto the truck with the highest units per box first, maximizing the number of units on the truck until it reaches its capacity.
This solution sorts the boxTypes array based on the units per box in descending order. Then, it iterates through the sorted array, adding as many boxes as possible from each type to the truck until the truck's capacity is reached. The function returns the total units accumulated.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) extra space, as we sort in place.
Instead of sorting by each unit's count, employ counting sort principles to store the total units in an array where the index represents the units per box. This could potentially be faster for large inputs with many boxes and limited unit types.
This approach uses a counting array where the index represents units per box to aggregate total boxes available. The truck is filled according to the highest units available in the count array.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + M) where M = 1000 is a constant.
Space Complexity: O(M) for the counting array.
| Approach | Complexity |
|---|---|
| Greedy Approach using Sorting | Time Complexity: O(n log n) due to sorting. |
| Counting Sort Based Approach | Time Complexity: O(n + M) where M = 1000 is a constant. |
Maximum Units on a Truck | maximum units on a truck | leetcode 1710 | array | Amazon • Naresh Gupta • 10,494 views views
Watch 9 more video solutions →Practice Maximum Units on a Truck with our built-in code editor and test cases.
Practice on FleetCode