Start learning free

LESSON 334 OF 348 · GREEDY

Maximum Units on a Truck in TypeScript: Greedy Sort by Density

Practice Greedy, O(n log n) Read the full explanation

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 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
STEP 1 OF 7
    Ctrl + Enter to check

    TYPESCRIPT · GREEDY

    Maximum Units On A Truck in TypeScript, explained

    Problem overview

    The method maximumUnits receives boxTypes, a list of [numberOfBoxes, numberOfUnitsPerBox] pairs, and truckSize, the maximum number of boxes the truck can hold. You choose which boxes to load, and the method returns the largest possible total of units.

    In the first example, boxTypes = [[1, 3], [2, 2], [3, 1]] and truckSize = 4. Take the one box with 3 units, then both boxes with 2 units each, then one of the boxes with 1 unit. The total is 3 + 4 + 1 = 8. In the second example, boxTypes = [[5, 10], [2, 5], [4, 7], [3, 9]] and truckSize = 10: the answer is 91.

    Approach: load the densest boxes first

    Every box takes exactly one slot on the truck, no matter how many units it holds. So there is no trade-off to weigh. Given a free slot, you should always fill it with the box that has the most units. That is a greedy argument: if an optimal load ever skipped a richer box for a poorer one, swapping them would not lower the total.

    The plan is to sort the box types by units per box, largest first, and then take as many boxes as possible from each type in turn until the truck is full.

    On the second example, sorting by units per box gives [[5, 10], [3, 9], [4, 7], [2, 5]]. The truck holds 10 boxes:

    • Take all 5 boxes of 10 units: 50 units, 5 slots left.
    • Take all 3 boxes of 9 units: 27 units, 2 slots left.
    • Take 2 of the 4 boxes of 7 units: 14 units, 0 slots left.

    The total is 50 + 27 + 14 = 91.

    Why sorting by box count fails

    It is tempting to load the biggest groups first, since they fill the truck quickly. On the second example it gives 50 + 28 + 9 = 87 instead of 91, because it loads the 7-unit boxes before the 9-unit ones. A smaller case makes the point sharper: with [[5, 1], [1, 100]] and truckSize = 5, loading the five-box group first yields 5 units, while taking the single 100-unit box first and four 1-unit boxes yields 104. Slots are the scarce resource, so units per box is the only thing that ranks the choices.

    Because boxes of the same type are interchangeable, taking a type partly is fine. If three boxes fit and the type has ten, you take three. There is never a reason to skip ahead and leave room unused while better or equal boxes remain.

    Step by step

    1. Sort boxTypes in place with a comparator that orders by the second element in decreasing order: b[1] - a[1].
    2. Declare units with let, starting at 0, for the running total.
    3. Loop over the sorted pairs with for...of, destructuring each into boxes and unitsPerBox.
    4. Compute how many boxes to take. It is the smaller of the boxes available and the room left, so Math.min(boxes, truckSize).
    5. Add take * unitsPerBox to units.
    6. Subtract take from truckSize so the variable always holds the free room. If it hits 0, break: nothing more fits.
    7. Return units.

    The solution in TypeScript

    class Solution {
    maximumUnits(boxTypes: number[][], truckSize: number): number {
        boxTypes.sort((a, b) => b[1] - a[1]);
        let units = 0;
        for (const [boxes, unitsPerBox] of boxTypes) {
            const take = Math.min(boxes, truckSize);
            units += take * unitsPerBox;
            truckSize -= take;
            if (truckSize === 0) {
                break;
            }
        }
        return units;
    }
}

    TypeScript details to notice:

    • The comparator. sort calls it with two elements, here two [boxes, unitsPerBox] arrays. A negative result puts a first, so b[1] - a[1] puts the larger units-per-box first. Without a comparator, sort would convert elements to strings and compare those, which is meaningless for pairs of numbers.
    • sort changes the caller's array. After the call on the second example, the caller's boxTypes reads [[5,10],[3,9],[4,7],[2,5]]. Copy first with [...boxTypes] if the original order matters.
    • Destructuring. const [boxes, unitsPerBox] unpacks the two elements of each pair. Using const is fine, because these names are never reassigned within an iteration.
    • Parameters can be reassigned. truckSize -= take changes the local parameter only. The caller's number is untouched, because numbers are passed by value.
    • No overflow. The constraints keep the total under 1000 * 1000 * 1000, far below the 2^53 limit up to which number holds integers exactly.

    Complexity

    Let m be the number of box types.

    Time: O(m log m). Sorting dominates. The loop that follows visits each type at most once.

    Space: O(1) extra, apart from whatever the engine uses internally to sort. The solution reorders the input in place and builds nothing new.

    The truck size can be as large as a million, but the loop never counts individual boxes: it takes a whole type at a time with Math.min, so the work depends on the number of types only.

    Edge cases and common mistakes

    • The truck is bigger than all boxes together. [[5, 10]] with truckSize = 100 returns 50. The loop ends without ever reaching zero room.
    • Few slots. [[5, 10], [1, 100]] with truckSize = 1 returns 100: the sort puts the dense single box first.
    • Sorting by the wrong field. Sorting by the number of boxes, a[0], is a common slip. The count says nothing about value per slot.
    • Sorting ascending. Writing a[1] - b[1] loads the poorest boxes first and gives a smaller total.
    • Taking a whole type regardless of room. Without the Math.min, the first example would load all 3 boxes of 1 unit and exceed the capacity.
    • Leaving out the break. The result would still be right, since take would be 0 for every remaining type. The break only saves iterations.

    Testing

    • [[1, 3], [2, 2], [3, 1]] with truckSize = 4 gives 8.
    • [[5, 10], [2, 5], [4, 7], [3, 9]] with truckSize = 10 gives 91.
    • [[5, 10]] with truckSize = 100 gives 50.
    • [[5, 10], [1, 100]] with truckSize = 1 gives 100.
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free