In this post we will discuss about Maximum Units on a Truck in detail and all the download resources are available at interviewquestionssurvey. Books, PDF and all other study materials can be downloaded from here in Hindi or English.
You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]:
numberOfBoxesiis the number of boxes of typei.numberOfUnitsPerBoxiis the number of units in each box of the typei.
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 <= 106
Maximum Units on a Truck Solution
Solution 1:
For this problem, we simply need to prioritize the more valuable boxes first. To do this, we should sort the boxtypes array (B) in descending order by the number of units per box (B[i][1]).
Then we can iterate through B and at each step, we should add as many of the boxes as we can, until we reach the truck size (T). We should add the number of boxes added multiplied by the units per box to our answer (ans), and decrease T by the same number of boxes.
Once the truck is full (T == 0), or once the iteration is done, we should return ans.
- Time Complexity: O(N log N) where N is the length of B, for the sort
- Space Complexity: O(1)
Maximum Units on a Truck JavaScript Code:
var maximumUnits = function(B, T) {
B.sort((a,b) => b[1] - a[1])
let ans = 0
for (let i = 0; T && i < B.length; i++) {
let count = Math.min(B[i][0], T)
ans += count * B[i][1], T -= count
}
return ans
};Maximum Units on a Truck Python Code:
class Solution:
def maximumUnits(self, B: List[List[int]], T: int) -> int:
B.sort(key=lambda x: x[1], reverse=True)
ans = 0
for b,n in B:
boxes = min(b, T)
ans += boxes * n
T -= boxes
if T == 0: return ans
return ansMaximum Units on a Truck Java Code:
class Solution {
public int maximumUnits(int[][] B, int T) {
Arrays.sort(B, (a,b) -> b[1] - a[1]);
int ans = 0;
for (int[] b : B) {
int count = Math.min(b[0], T);
ans += count * b[1];
T -= count;
if (T == 0) return ans;
}
return ans;
}
}Maximum Units on a Truck C++ Code:
class Solution {
public:
int maximumUnits(vector<vector<int>>& B, int T) {
sort(B.begin(), B.end(), [](auto& a, auto& b) { return b[1] < a[1];});
int ans = 0;
for (auto& b : B) {
int count = min(b[0], T);
ans += count * b[1], T -= count;
if (!T) return ans;
}
return ans;
}
};Solution 2:
We can easiliy observe that it will always be better to choose the box with maximum number of units in it so that the overall number of units that can be put on truck is maximized.
Thus, we will sort the given boxTypes array based on number of units in each box. Then we greedily keep choosing the boxes starting from the first one from the sorted array till we fill the whole truck.
Maximum Units on a Truck C++
int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
sort(begin(boxTypes), end(boxTypes), [](auto& a, auto& b){ return a[1] > b[1];}); // sort by number of units / box
int maxUnits = 0;
for(auto& box : boxTypes) {
if(truckSize <= 0) break; // keep choosing greedily till you run out of truckSize
maxUnits += min(truckSize, box[0]) * box[1]; // add (no of box * units) in that box
truckSize -= box[0];
}
return maxUnits;
}
Maximum Units on a Truck Python
def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
boxTypes.sort(key=lambda a:-a[1])
max_units = 0
for box in boxTypes:
if truckSize < 0 : break
max_units += min(truckSize, box[0]) * box[1]
truckSize -= box[0]
return max_units
Time Complexity : O(NlogN), where N is the number of elements in boxTypes
Space Complexity : O(1), we are always using constant amount of space (ignoring the space required by the sort algorithm)
Solution 3:
The given constraints for numberOfUnitsPerBox are small enough that we can use an approach similar to counting sort to reduce the time complexity to O(N).
Here, we can declare an array freq of size=1000 (which is maximum number of units per box) where freq[i] will denote the number of boxes that can hold i number of units. We can iterate through the given boxTypes array and populate the freq array. Then we can iterate over the freq array and greedily choose starting from i=1000 till we run out of truckSize or pick all available boxes.
Maximum Units on a Truck C++
int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
int freq[1001]{0}, maxUnits = 0; // freq[i] = number of boxes that can hold i units
for(auto& box : boxTypes) freq[box[1]] += box[0];
// greedily choose starting from max units till either truckSize runs out or you choose all boxes
for(int units = 1000; truckSize > 0 && ~units; --units) {
maxUnits += min(truckSize, freq[units]) * units;
truckSize -= freq[units];
}
return maxUnits;
}Maximum Units on a Truck Python
def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
freq, max_units = [0]*1001, 0
for box in boxTypes:
freq[box[1]] += box[0]
for units in range(1000,0,-1):
if truckSize < 0: break
max_units += min(truckSize, freq[units]) * units
truckSize -= freq[units]
return max_unitsTime Complexity : O(N)
Space Complexity : O(1)