algoadvance

Leetcode 1710. Maximum Units on a Truck

Problem Statement

1710. Maximum Units on a Truck

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

You are also given an integer truckSize, which represents the maximum number of boxes that can be put on the truck.

You need to return the maximum total number of units that can be put on the truck.

Example:

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) = 3 + 4 + 1 = 8.

Clarifying Questions:

  1. What is the size of boxTypes?
    • It is reasonable to assume boxTypes will fit in memory.
  2. Are there any constraints on the values of numberOfBoxes_i, numberOfUnitsPerBox_i, and truckSize?
    • The constraints are provided in the problem statement on LeetCode.
  3. Can boxTypes be empty or can truckSize be zero?
    • Yes, in such cases, the output should be zero since no boxes can be loaded.

Strategy

  1. Sort boxTypes by the number of units per box in descending order.
  2. Iterate through the sorted boxTypes:
    • Take as many boxes of the current type as possible until the truck is full.
  3. Maintain a running total of the units loaded onto the truck.
  4. Stop when the truck reaches its full capacity.

Code

Let’s implement this approach in C++:

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
        // Sort the boxTypes based on the second element in descending order
        sort(boxTypes.begin(), boxTypes.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] > b[1];
        });

        int maxUnits = 0;
        for (const auto& box : boxTypes) {
            int numBoxes = box[0];
            int unitsPerBox = box[1];
            
            if (truckSize >= numBoxes) {
                // If all boxes of this type can be loaded
                maxUnits += numBoxes * unitsPerBox;
                truckSize -= numBoxes;
            } else {
                // If only part of the boxes can be loaded
                maxUnits += truckSize * unitsPerBox;
                break; // Truck is now full
            }
        }
        
        return maxUnits;
    }
};

Time Complexity

Thus, the overall time complexity is O(n log n) due to the sorting operation. The space complexity is O(1) if we do not account for the input storage.

Explanation:

  1. Sorting: Sorting the boxTypes array by units per box in descending order ensures that we maximize the units loaded per space on the truck.
  2. Iterating Through the Boxes: For each type of box, we determine how many of those boxes can be loaded given the available capacity of the truck and add the corresponding units.
  3. Stopping once Full: If the truck reaches its full capacity, we stop further loading.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI