Start learning free

LESSON 358 OF 414 · GREEDY

Maximum Units on a Truck in Scala: Greedy Sort by Units per Box

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 <= (number of box types) <= 1000
  • 1 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000
  • 1 <= truckSize <= 106
STEP 1 OF 7
    Ctrl + Enter to check

    SCALA · GREEDY

    Maximum Units On A Truck in Scala, explained

    Problem overview

    The method maximumUnits receives boxTypes, an Array[Array[Int]] in which each entry is [numberOfBoxes, unitsPerBox], and truckSize, the most boxes the truck can carry. It returns the largest total number of units that fit on the truck.

    In the first example, boxTypes = [[1, 3], [2, 2], [3, 1]] and truckSize = 4. Take the one box with 3 units, the two boxes with 2 units, and one of the boxes with 1 unit: 3 + 4 + 1 = 8. In the second example, [[5, 10], [2, 5], [4, 7], [3, 9]] with truckSize = 10, the answer is 91. The constraints allow up to 1000 box types and up to 1000 boxes of each type, and a truck of up to a million boxes.

    Approach: densest boxes first

    Every box takes exactly one slot, whatever it holds. So each slot should carry the box with the most units available. That makes a greedy strategy correct: sort the box types by units per box, largest first, then load from the front until the truck is full.

    Swapping a loaded box for one with more units never reduces the total, and never uses an extra slot, so no better plan can skip a denser box in favour of a lighter one. The number of boxes per type only limits how many of that type you can take.

    Trace the first example. Sorted by units per box, the order is already [1, 3], [2, 2], [3, 1]. The first type contributes 1 box (3 units) and leaves 3 slots, the second contributes 2 boxes (4 units) and leaves 1, and the third contributes min(3, 1) = 1 box (1 unit) and leaves 0. The total is 8.

    The second example works the same way. Sorted from most to fewest units per box, the types are [5, 10], [3, 9], [4, 7] and [2, 5]. The first takes 5 boxes for 50 units and leaves 5 slots. The second takes all 3 boxes for 27 more units, 77 in total, and leaves 2 slots. The third takes only 2 of its 4 boxes, for 14 units, which brings the total to 91. The last type then takes 0 boxes.

    Step by step

    1. Sort by units per box, largest first. sortBy sorts by the key its function returns, in increasing order, so the key is the negative of the units: -b(1). The result goes into a new array, sorted.
    2. Set up two vars. units is the running total, starting at 0. remaining starts at truckSize. Parameters can't be reassigned in Scala, so the changing capacity lives in its own variable.
    3. Loop over sorted, with each box being a [count, unitsPerBox] pair: box(0) is how many boxes of the type exist and box(1) is the units in each.
    4. Decide how many to take: math.min(box(0), remaining). You can't take more than exist or more than still fit.
    5. Add the units that those boxes contribute: take * box(1).
    6. Use up the capacity by subtracting take from remaining. Scala has no break statement, so the loop simply keeps going. Once remaining is 0 every later take is 0 and adds nothing.
    7. End with units as the last expression.

    The solution in Scala

    class Solution {
    def maximumUnits(boxTypes: Array[Array[Int]], truckSize: Int): Int = {
        val sorted = boxTypes.sortBy(b => -b(1))
        var units = 0
        var remaining = truckSize
        for (box <- sorted) {
            val take = math.min(box(0), remaining)
            units += take * box(1)
            remaining -= take
        }
        units
    }
}

    The Scala details worth a closer look:

    • sortBy returns a new array. The caller's boxTypes keeps its original order. The sort is stable, so box types with equal units keep their relative order, which doesn't change the total.
    • Sorting in decreasing order. sortBy has no direction option, so negating the key is the quickest way. Because the units are at most 1000, the negation can't overflow. Reversing the sorted array also works.
    • Int is enough. It has 32 bits and wraps silently on overflow. The largest possible total is a million boxes times 1000 units, which is 1,000,000,000. That is below the Int limit of 2,147,483,647.
    • Lambda shorthand. b => -b(1) is an anonymous function that takes a box type and returns its sort key.

    Complexity

    Let n be the number of box types.

    Time: O(n log n). Sorting dominates. The loop is O(n).

    Space: O(n). sortBy builds a new array of the same length. The array holds references to the original pairs rather than copies of them.

    Edge cases and common mistakes

    • A truck bigger than the load. [[1, 5]] with truckSize = 10 returns 5. The truck is not filled, and remaining ends at 9.
    • A truck smaller than one type. [[5, 10]] with truckSize = 2 returns 20, because take is capped by remaining.
    • The largest input. With 1000 types of 1000 boxes holding 1000 units each and truckSize = 1000000, the result is 1000000000, with no overflow.
    • Sorting by box count. The first element is how many boxes exist, not how valuable they are. Sorting by b(0) gives wrong answers.
    • Forgetting the negative sign. Without it the sort is increasing, and the truck fills with the lightest boxes first.
    • Multiplying before capping. Use take, not box(0), when adding units.

    Testing

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