Code Implementation

class Solution:
    def maximumUnits(self, boxTypes, truckSize):
        # Sort the boxTypes by units per box in descending order
        boxTypes.sort(key=lambda x: x[1], reverse=True)
        total_units = 0
        for boxes, units_per_box in boxTypes:
            # Take as many boxes as possible, up to truckSize
            take = min(truckSize, boxes)
            total_units += take * units_per_box
            truckSize -= take
            if truckSize == 0:
                break
        return total_units
      

class Solution {
public:
    int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
        // Sort by units per box in descending order
        sort(boxTypes.begin(), boxTypes.end(),
             [](const vector<int>& a, const vector<int>& b) {
                 return a[1] > b[1];
             });
        int total_units = 0;
        for (const auto& box : boxTypes) {
            int boxes = box[0];
            int units_per_box = box[1];
            int take = min(truckSize, boxes);
            total_units += take * units_per_box;
            truckSize -= take;
            if (truckSize == 0) break;
        }
        return total_units;
    }
};
      

class Solution {
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        // Sort by units per box in descending order
        Arrays.sort(boxTypes, (a, b) -> b[1] - a[1]);
        int totalUnits = 0;
        for (int[] box : boxTypes) {
            int boxes = box[0];
            int unitsPerBox = box[1];
            int take = Math.min(truckSize, boxes);
            totalUnits += take * unitsPerBox;
            truckSize -= take;
            if (truckSize == 0) break;
        }
        return totalUnits;
    }
}
      

var maximumUnits = function(boxTypes, truckSize) {
    // Sort by units per box in descending order
    boxTypes.sort((a, b) => b[1] - a[1]);
    let totalUnits = 0;
    for (let [boxes, unitsPerBox] of boxTypes) {
        let take = Math.min(truckSize, boxes);
        totalUnits += take * unitsPerBox;
        truckSize -= take;
        if (truckSize === 0) break;
    }
    return totalUnits;
};
      

Problem Description

You are given an array boxTypes, where each element is a pair [numberOfBoxes, unitsPerBox]. This means there are numberOfBoxes boxes, and each box contains unitsPerBox units. You also have a truck that can carry at most truckSize boxes in total.

Your goal is to load the truck with boxes so that the total number of units on the truck is maximized. You can only take whole boxes from each type, and you cannot split boxes. You cannot take more boxes than are available for any type, and the sum of all boxes loaded cannot exceed truckSize.

The problem guarantees that there is only one valid solution for each input, and you cannot reuse or split boxes.

Thought Process

At first glance, this problem seems like it could be solved by trying all possible combinations of boxes, but that would be very inefficient. Instead, we should focus on maximizing the number of units we can load onto the truck.

Since each box type has a different number of units per box, it makes sense to prioritize box types that give us the most units for each box we load. By always choosing the box type with the highest units per box first, we can ensure that every box we load contributes as much as possible to our total.

This greedy approach means we don't need to consider all combinations—just sort the box types by units per box and take as many from the best as we can, then move to the next.

Solution Approach

• Step 1: Sort the boxTypes array in descending order based on unitsPerBox. This ensures that we always consider the most valuable boxes first.
• Step 2: Initialize a variable to keep track of the total units loaded onto the truck.
• Step 3: Iterate over the sorted boxTypes array. For each type:
  • Determine the number of boxes to take: it's the minimum between the remaining truckSize and the number of boxes available for that type.
  • Add the units contributed by these boxes to the total.
  • Subtract the number of boxes taken from truckSize.
  • If the truck is full (truckSize reaches zero), stop.
• Step 4: Return the total units loaded onto the truck.

This approach is greedy because we always pick the best available option at each step. Sorting is used because lookups and insertions are efficient, and we only need to pass through the sorted list once.

Example Walkthrough

Suppose boxTypes = [[1,3],[2,2],[3,1]] and truckSize = 4.

• First, sort by units per box: [[1,3],[2,2],[3,1]] (already sorted).
• Start with 0 units and 4 spaces on the truck.
• Take 1 box from [1,3] (since only 1 available). Now truckSize = 3, total units = 3.
• Take 2 boxes from [2,2] (since 2 available, and truckSize = 3). Now truckSize = 1, total units = 3 + 2*2 = 7.
• Take 1 box from [3,1] (since only 1 space left). Now truckSize = 0, total units = 7 + 1*1 = 8.
• Truck is full. Return 8.

At each step, we always chose the box type with the highest units per box first, and filled the truck as much as possible.

Time and Space Complexity

Brute-force approach: If we tried every possible combination, the time complexity would be exponential, as we'd have to consider all subsets of boxes.

Optimized (Greedy) approach:

• Sorting the array takes O(n \log n), where n is the number of box types.
• The single pass through the array is O(n).
• So the overall time complexity is O(n \log n).
• The space complexity is O(1) if sorting in-place, or O(n) if not.

Summary

The key to maximizing the number of units on the truck is to always load boxes with the most units first. By sorting the box types and greedily filling the truck, we ensure each slot is used as efficiently as possible. This leads to a simple, elegant solution that is both easy to understand and efficient to run.