Problem overview
The method maximumUnits receives boxTypes, an array of pairs, and an integer truckSize. Each pair is [numberOfBoxes, numberOfUnitsPerBox]: how many boxes of that type exist and how many units each one holds. The truck carries at most truckSize boxes in total, and the task is to load boxes so that the total number of units is as large as possible.
In the first example, boxTypes = [[1, 3], [2, 2], [3, 1]] and truckSize = 4. Take the single 3-unit box, both 2-unit boxes, and one of the 1-unit boxes. That is 4 boxes and 3 + 2 + 2 + 1 = 8 units. In the second example the answer is 91 for [[5, 10], [2, 5], [4, 7], [3, 9]] with truckSize = 10.
Approach: always load the densest boxes first
The truck is limited by the number of boxes, not by their weight or size. Every box uses exactly one slot, whatever it contains. So the best use of a slot is always the box that holds the most units.
That gives a greedy rule: sort the box types by units per box, largest first, and take as many boxes as possible from each type in that order, until the truck is full. Why can this not be beaten? Suppose a loading skips a box with more units in favour of one with fewer. Swapping the two keeps the box count the same and does not lower the total, so a best loading can always be rearranged to take the densest boxes first.
The alternative is to try combinations of boxes. With up to 1,000 box types, each with up to 1,000 boxes, that explodes. Sorting turns the problem into a single pass.
Step by step
- Sort
boxTypesby units per box, descending. The comparator receives two pairs,aandb, and returnsb[1] - a[1]. A positive result putsaafterb, so the larger second value ends up first. The sort happens in place. - Declare
unitswithletand set it to 0. It is the running total. - Loop over the sorted types with
for (const [boxes, unitsPerBox] of boxTypes). The square brackets unpack each pair into two named values. - Decide how many boxes to take.
Math.min(boxes, truckSize)is limited by the supply of this type and by the room left on the truck. - Add to the total and use up the room. Add
take * unitsPerBoxtounitsand subtracttakefromtruckSize. The parameter is reused as a "space left" counter. - Stop when the truck is full. If
truckSize === 0,break. The loop would give the same result without this check, since later iterations would take 0 boxes, but breaking avoids pointless work. - Return
units.
On the first example, sorting by the second value descending gives [[1, 3], [2, 2], [3, 1]], which is already in order. Take 1 box (3 units, 3 slots left), then 2 boxes (4 units, 1 slot left), then Math.min(3, 1) = 1 box (1 unit, 0 slots left). The total is 8 and the loop breaks.
The solution in JavaScript
class Solution {
/**
* @param {number[][]} boxTypes
* @param {number} truckSize
* @return {number}
*/
maximumUnits(boxTypes, truckSize) {
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;
}
}
JavaScript details worth knowing:
- The comparator.
Array.prototype.sortwith no comparator turns elements into strings and compares them as text. For these pairs that would be meaningless. A comparator returning a negative number keepsabeforeb, a positive one puts it after, and zero treats them as equal. Subtracting works here because all values are small integers. Writinga[1] - b[1]instead would sort ascending. - In-place sorting.
sortchanges the array it is called on and also returns it. The caller'sboxTypesends up reordered. That is acceptable for this lesson, but copy it first with[...boxTypes]if the original order matters. - The sort is stable. Since ES2019, equal elements keep their original relative order. Two box types with the same density can be loaded in either order without changing the total, so stability is not needed here.
- Destructuring in
for...of.const [boxes, unitsPerBox]unpacks an array of two values into two variables in one step. It is the same as readingpair[0]andpair[1]. - Parameters are ordinary variables.
truckSize -= takereassigns the local parameter. The caller's variable is unaffected because numbers are passed by value. - Numbers stay safe. At most 1,000 types with at most 1,000 boxes each means at most 1,000,000 boxes, each holding at most 1,000 units. The total is therefore at most one billion, far below
Number.MAX_SAFE_INTEGER, which is about 9 quadrillion.
Complexity
Let n be the number of box types.
Time: O(n log n). Sorting dominates. The loop afterwards is a single pass of O(n).
Space: O(log n) or O(n). The sort works on the array in place, and the working memory it needs depends on the engine's sorting algorithm, so a safe description is "small extra memory". The loop adds only a few variables.
Edge cases and common mistakes
- More room than boxes. With
boxTypes = [[1, 3]]andtruckSize = 10the loop takes the one box and finishes without hittingbreak. The answer is 3. - Taking too many boxes. Using
boxesinstead ofMath.min(boxes, truckSize)would overload the truck as soon as one type has more boxes than the room left. - Sorting by the wrong column. The first column is the box count and is irrelevant for the order. Sorting on
a[0]or sorting ascending gives wrong totals. - Forgetting the comparator. A default sort compares the pairs as text, such as
"5,10"against"2,5", which does not order them by units. - Forgetting to reduce
truckSize. Without it every type would take its full count and the limit would be ignored. - Exactly full. When
truckSizeequals the total number of boxes, every box is loaded and the answer is the sum of all units.
Testing
boxTypes = [[1, 3], [2, 2], [3, 1]],truckSize = 4gives8.boxTypes = [[5, 10], [2, 5], [4, 7], [3, 9]],truckSize = 10gives91.boxTypes = [[1, 3]],truckSize = 10gives3.