Start learning free

LESSON 334 OF 348 · GREEDY

Maximum Units on a Truck in Kotlin: Greedy 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 <= boxTypes.length <= 1000
  • 1 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000
  • 1 <= truckSize <= 106
STEP 1 OF 7
    Ctrl + Enter to check

    KOTLIN · GREEDY

    Maximum Units On A Truck in Kotlin, explained

    Problem overview

    The function maximumUnits receives boxTypes, an Array<IntArray> in which each entry is [numberOfBoxes, numberOfUnitsPerBox], and truckSize, the maximum number of boxes the truck can carry. You may take any boxes you like, as long as the total count stays within truckSize. The function 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, both boxes with 2 units, and one of the three boxes with 1 unit: 1 * 3 + 2 * 2 + 1 * 1 = 8.

    Approach: load the densest boxes first

    The truck is limited by the number of boxes, not by their weight or size, so every box costs exactly one slot. A slot is best spent on the box that holds the most units. That makes the greedy rule obvious: sort the box types by units per box, from most to fewest, and take as many boxes as possible from each type until the truck is full.

    The rule is correct because of an exchange argument. Suppose an optimal load contains a box with fewer units while a box with more units is left behind. Swapping one for the other keeps the same box count and does not lower the total. So you can always change an optimal load into the greedy one without losing units.

    A brute-force search over every way to pick boxes explodes quickly. The greedy approach needs only a sort and one pass over the box types.

    Take the second example, [[5, 10], [2, 5], [4, 7], [3, 9]] with truckSize = 10. Sorted by units per box, the order is the 10-unit boxes, the 9-unit boxes, the 7-unit boxes, then the 5-unit boxes. Take all 5 of the first type for 50 units, leaving 5 slots. Take all 3 of the second for 27 more, leaving 2 slots. Take 2 of the 4 boxes in the third type for 14 more. The truck is full, and the total is 91.

    Step by step

    1. Sort boxTypes by units per box, largest first. The units are in position 1 of each entry, and the sort happens in place.
    2. Declare units as a var starting at 0 for the running total. Also declare remaining as a var copy of truckSize, because a function parameter can't be reassigned.
    3. Loop over the box types with each entry bound to box. Position 0 is how many boxes of that type exist, and position 1 is the units in each.
    4. Decide how many to take. It is the smaller of the boxes available and the slots remaining, since neither limit may be exceeded.
    5. Add the units. The boxes taken times the units per box is what this type contributes.
    6. Update the free space and stop early. Subtract what was taken from remaining, and leave the loop once it reaches 0. The loop would end correctly without the break, because take would be 0 from then on, but breaking avoids pointless iterations.
    7. Return units.

    The solution in Kotlin

    class Solution {
    fun maximumUnits(boxTypes: Array<IntArray>, truckSize: Int): Int {
        boxTypes.sortByDescending { it[1] }
        var units = 0
        var remaining = truckSize
        for (box in boxTypes) {
            val take = minOf(box[0], remaining)
            units += take * box[1]
            remaining -= take
            if (remaining == 0) {
                break
            }
        }
        return units
    }
}

    The Kotlin details worth a closer look:

    • sortByDescending { it[1] } sorts the array in place. The lambda picks the sort key: inside a lambda with a single parameter, it is the current element, here one IntArray, and it[1] is its units per box. Entries with equal keys keep their relative order, since the sort is stable.
    • In place, so the caller's array changes. After the call, boxTypes is reordered. After sortedByDescending, by contrast, you would get a new list and leave the original alone. Here the in-place version is fine because the function does not need the original order.
    • Array<IntArray> is an array of arrays. Each inner IntArray holds a primitive pair, read with box[0] and box[1].
    • minOf(a, b) returns the smaller of two values without any import.
    • val take inside the loop is a fresh read-only value for each iteration, while units and remaining, which change across iterations, are var.
    • break ends the innermost loop, here the for.

    Complexity

    Time: O(m log m), where m is the number of box types. Sorting dominates; the loop afterwards is O(m).

    Space: O(1) extra beyond the input, apart from whatever the sort uses internally. The code adds only a few integers.

    Edge cases and common mistakes

    • Truck smaller than the first type. [[5, 10]] with truckSize = 3 returns 30: take is the smaller of 5 and 3, so you load three boxes and leave two behind.
    • Truck larger than everything. [[2, 4]] with truckSize = 100 returns 8. The loop ends when the box types run out, with slots still free.
    • Sorting by the wrong field. Sorting by it[0], the number of boxes, ranks types by how many exist, not by how valuable each box is.
    • Sorting in ascending order. That loads the lightest boxes first and gives a smaller total.
    • Confusing boxes with units. truckSize limits boxes, so remaining drops by take, not by take * box[1].
    • Overflow. The result fits comfortably in an Int under the lesson's limits: at most 1,000 types of 1,000 boxes with 1,000 units each is 1,000,000,000 units, below the Int maximum of 2,147,483,647.

    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 = 3 gives 30.
    • [[2, 4]] with truckSize = 100 gives 8.
    • [[3, 2], [3, 2]] with truckSize = 4 gives 8.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free