Solution: Maximum Units on a Truck

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #1710 (Easy): Maximum Units on a Truck

---

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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

• numberOfBoxes i is the number of boxes of type i.
• numberOfUnitsPerBox i 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.

---

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 * 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 <= 10^6

---

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

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)

---

Javascript Code:

(Jump to: Problem Description || Solution Idea)

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
};

---

Python Code:

(Jump to: Problem Description || Solution Idea)

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 ans

---

Java Code:

(Jump to: Problem Description || Solution Idea)

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;
    }
}

---

C++ Code:

(Jump to: Problem Description || Solution Idea)

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;
    }
};