# Maximum Units on a Truck
**Difficulty:** EASY
[External](https://leetcode.com/problems/maximum-units-on-a-truck)
Canonical: https://scaleengineer.com/dsa/problems/maximum-units-on-a-truck
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [IBM](https://scaleengineer.com/companies/ibm), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Arista Networks](https://scaleengineer.com/companies/arista-networks)
---
## Problem
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`

# Approaches
## Greedy Approach with Sorting
This approach is based on the greedy principle that to maximize the total units, we should always prioritize loading the boxes that offer the most units. By sorting the box types in descending order based on the number of units per box, we can iteratively fill the truck with the most valuable boxes first.
**Time:** O(N log N), where N is the number of box types (`boxTypes.length`). The sorting step dominates the time complexity. The subsequent loop runs at most N times. · **Space:** O(log N) or O(N), depending on the implementation of the sorting algorithm used. In Java, `Arrays.sort` for objects uses TimSort, which requires O(N) space in the worst case.
**Pros:** Relatively simple and intuitive to implement.; Correctly solves the problem by following a greedy strategy.
**Cons:** The O(N log N) time complexity from sorting is not the most optimal solution possible for this problem's constraints.
### Explanation
The core idea is to be greedy. We want to load the boxes that give us the maximum number of units.

First, we sort the `boxTypes` array. The sorting criterion is the number of units per box (`boxTypes[i][1]`) in descending order. This ensures that we consider the most "unit-dense" boxes first.

After sorting, we iterate through the sorted list of box types.

In each iteration, we check the remaining capacity of the truck (`truckSize`).

We take as many boxes of the current type as we can. The number of boxes to take is the minimum of the available boxes of that type and the remaining truck capacity.

We add the units from the loaded boxes to our total count and decrease the `truckSize` by the number of boxes we loaded.

We continue this process until we have either considered all box types or the truck is full (`truckSize` is 0).

Finally, we return the total accumulated units.

```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        // Sort the boxTypes array in descending order of units per box.
        Arrays.sort(boxTypes, (a, b) -> b[1] - a[1]);

        int totalUnits = 0;
        for (int[] boxType : boxTypes) {
            int numberOfBoxes = boxType[0];
            int unitsPerBox = boxType[1];

            // Determine how many boxes of this type to take.
            int boxesToTake = Math.min(numberOfBoxes, truckSize);

            totalUnits += boxesToTake * unitsPerBox;
            truckSize -= boxesToTake;

            // If the truck is full, we can stop.
            if (truckSize == 0) {
                break;
            }
        }
        return totalUnits;
    }
}
```
### Algorithm
*   Sort the `boxTypes` 2D array in descending order based on the second element (units per box).
*   Initialize a variable `totalUnits` to 0.
*   Iterate through the sorted `boxTypes` array.
*   For each `boxType`, get the `numberOfBoxes` and `unitsPerBox`.
*   Calculate the number of boxes to load for the current type: `boxesToTake = min(numberOfBoxes, remaining truckSize)`.
*   Add the units to the total: `totalUnits += boxesToTake * unitsPerBox`.
*   Update the remaining truck size: `truckSize -= boxesToTake`.
*   If `truckSize` becomes 0, break the loop.
*   Return `totalUnits`.

## Greedy Approach with Counting Sort
This approach improves upon the sorting method by recognizing that the number of units per box is constrained to a small range (1 to 1000). Instead of a general-purpose comparison sort, we can use a more efficient, non-comparison-based sorting technique like Counting Sort (or Bucket Sort). This allows us to group boxes by their unit count and process them in descending order of units without an O(N log N) sorting overhead.
**Time:** O(N + M), where N is the number of box types and M is the maximum possible units per box (1001). The first loop takes O(N) to populate the buckets. The second loop takes O(M) to iterate through the buckets. Since M is a constant, the overall complexity is linear, O(N). · **Space:** O(M), for the bucket array, where M is the maximum possible units per box (1001). Since M is a constant, this is considered O(1) constant space.
**Pros:** Highly efficient with linear time complexity, which is better than the sorting approach.; Constant space complexity as the size of the bucket array is fixed.
**Cons:** This approach is only efficient because the range of `unitsPerBox` is small and known. If the range were very large, this method would become impractical due to high space requirements.
### Explanation
The key observation is that `numberOfUnitsPerBox` is between 1 and 1000. This limited range allows for a linear time sorting algorithm.

We create an array, let's call it `bucket`, of size 1001. `bucket[i]` will store the total count of boxes that contain `i` units each.

We iterate through the input `boxTypes`. For each `[numberOfBoxes, unitsPerBox]`, we update our bucket: `bucket[unitsPerBox] += numberOfBoxes`. After this step, `bucket` effectively stores all boxes, grouped and counted by their unit value.

Next, we iterate through our `bucket` array, but in reverse order (from 1000 down to 1), because we want to load the boxes with the most units first.

For each unit value `i`, we check if `bucket[i]` has any boxes.

If it does, we determine how many boxes to take: `boxesToTake = Math.min(truckSize, bucket[i])`.

We update our `totalUnits` by `boxesToTake * i` and decrease `truckSize` by `boxesToTake`.

If `truckSize` reaches 0, we have filled the truck, and we can stop and return the result.

This method avoids the O(N log N) sort and achieves a linear time complexity.

```java
class Solution {
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        // Create a bucket array to count boxes for each unit value.
        // The maximum number of units per box is 1000.
        int[] bucket = new int[1001];
        for (int[] boxType : boxTypes) {
            int numberOfBoxes = boxType[0];
            int unitsPerBox = boxType[1];
            bucket[unitsPerBox] += numberOfBoxes;
        }

        int totalUnits = 0;
        // Iterate from the highest unit count down to the lowest.
        for (int units = 1000; units >= 1; units--) {
            // If there are boxes with this unit count.
            if (bucket[units] > 0) {
                // Determine how many boxes of this type to take.
                int boxesToTake = Math.min(bucket[units], truckSize);
                
                totalUnits += boxesToTake * units;
                truckSize -= boxesToTake;

                // If the truck is full, we can stop.
                if (truckSize == 0) {
                    break;
                }
            }
        }
        return totalUnits;
    }
}
```
### Algorithm
*   Create an integer array `bucket` of size 1001, initialized to zeros.
*   Iterate through the `boxTypes` array. For each `[numberOfBoxes, unitsPerBox]`, add `numberOfBoxes` to `bucket[unitsPerBox]`.
*   Initialize `totalUnits` to 0.
*   Iterate from `i = 1000` down to 1.
*   If `bucket[i]` is greater than 0:
    a.  Calculate the number of boxes to load: `boxesToTake = min(bucket[i], remaining truckSize)`.
    b.  Add the units to the total: `totalUnits += boxesToTake * i`.
    c.  Update the remaining truck size: `truckSize -= boxesToTake`.
    d.  If `truckSize` becomes 0, break the loop.
*   Return `totalUnits`.

# Solutions
### Java

```java
class Solution {
public
  int maximumUnits(int[][] boxTypes, int truckSize) {
    Arrays.sort(boxTypes, (a, b)->b[1] - a[1]);
    int ans = 0;
    for (var e : boxTypes) {
      int a = e[0], b = e[1];
      ans += b * Math.min(truckSize, a);
      truckSize -= a;
      if (truckSize <= 0) {
        break;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximumUnits(vector<vector<int>> &boxTypes, int truckSize) {
    sort(boxTypes.begin(), boxTypes.end(),
         [](auto &a, auto &b) { return a[1] > b[1]; });
    int ans = 0;
    for (auto &e : boxTypes) {
      int a = e[0], b = e[1];
      ans += b * min(truckSize, a);
      truckSize -= a;
      if (truckSize <= 0)
        break;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int: ans = 0 for a, b in sorted(boxTypes, key=lambda x: - x[1]): ans += b * min(truckSize, a) truckSize -= a if truckSize <= 0: break return ans

```