# Maximum Units on a Truck Solution

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]`:

• `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 <= 1000`
• `1 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000`
• `1 <= 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]).

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 - a)
let ans = 0
for (let i = 0; T && i < B.length; i++) {
let count = Math.min(B[i], T)
ans += count * B[i], 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, reverse=True)
ans = 0
for b,n in B:
boxes = min(b, T)
ans += boxes * n
T -= boxes
if T == 0: return ans
return ans``````

#### Maximum Units on a Truck Java Code:

``````class Solution {
public int maximumUnits(int[][] B, int T) {
Arrays.sort(B, (a,b) -> b - a);
int ans = 0;
for (int[] b : B) {
int count = Math.min(b, T);
ans += count * b;
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 < a;});
int ans = 0;
for (auto& b : B) {
int count = min(b, T);
ans += count * b, 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 > b;}); // 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) * box; // add (no of box * units) in that box
truckSize -= box;
}
return maxUnits;
}
``````

#### Maximum Units on a Truck Python

``````def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
boxTypes.sort(key=lambda a:-a)
max_units = 0
for box in boxTypes:
if truckSize < 0 : break
max_units += min(truckSize, box) * box
truckSize -= box
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{0}, maxUnits = 0;   // freq[i] = number of boxes that can hold i units
for(auto& box : boxTypes) freq[box] += box;
// 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 = *1001, 0
for box in boxTypes:
freq[box] += box
for units in range(1000,0,-1):
if truckSize < 0: break
max_units += min(truckSize, freq[units]) * units
truckSize -= freq[units]
return max_units``````

Time Complexity : `O(N)`
Space Complexity : `O(1)`