Maximum Units on a Truck

Easy Arrays & Hashing Greedy Original on LeetCode

Maximum Units on a Truck is a easy arrays & hashing problem solved with the greedy pattern. The best approach, optimal (bucket boxes by units), runs in O(n + U) time and O(U) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (repeatedly pick the best remaining type) up.

Problem

You need to load boxes onto a truck. boxTypes[i] = [numberOfBoxes_i, unitsPerBox_i] says that there are numberOfBoxes_i boxes of type i, and each of them holds unitsPerBox_i units.

The truck can carry at most truckSize boxes, whatever their type. Choose which boxes to load and return the largest total number of units the truck can carry.

Examples

Example 1

Input
boxTypes = [[2, 5], [4, 3], [1, 8]], truckSize = 4
Output
21
Why
Load the box with 8 units, both boxes with 5 units, and one box with 3 units: 8 + 5 + 5 + 3 = 21.

Example 2

Input
boxTypes = [[3, 2], [3, 2]], truckSize = 10
Output
12
Why
All 6 boxes fit, carrying 6 × 2 = 12 units.

Constraints

  • 1 <= boxTypes.length <= 1000
  • 1 <= numberOfBoxes_i, unitsPerBox_i <= 1000
  • 1 <= truckSize <= 10^6

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (repeatedly pick the best remaining type)O(n²)O(n)
Sort by units, then greedyO(n log n)O(1)
Optimal (bucket boxes by units)O(n + U)O(U)

1Brute force (repeatedly pick the best remaining type)

TimeO(n²)Up to n rounds, each scanning n types.
SpaceO(n)The used flags.

While the truck has room, scan all box types for the one with the most units per box that still has boxes, load as many of it as fit, and mark it used.

  1. Keep a used flag per type.
  2. While space remains: find the unused type with the largest unitsPerBox; stop if none.
  3. Load take = min(count, space) boxes; add take * units; subtract take from space; mark the type used.
class Solution {
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        int n = boxTypes.length, space = truckSize, total = 0;
        boolean[] used = new boolean[n];
        while (space > 0) {
            int best = -1;
            for (int i = 0; i < n; i++)
                if (!used[i] && (best == -1 || boxTypes[i][1] > boxTypes[best][1])) best = i;
            if (best == -1) break;
            used[best] = true;
            int take = Math.min(boxTypes[best][0], space);
            total += take * boxTypes[best][1];
            space -= take;
        }
        return total;
    }
}

2Sort by units, then greedy

TimeO(n log n)Sorting dominates; the greedy pass is linear.
SpaceO(1)Sorts in place (ignoring the sort's internal stack).

Sort the box types by units per box in decreasing order once, then load greedily from the front until the truck is full.

  1. Sort boxTypes by unitsPerBox descending.
  2. For each type: take = min(count, space); add take * units; reduce space; stop when space is 0.
class Solution {
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        Arrays.sort(boxTypes, (a, b) -> b[1] - a[1]);
        int space = truckSize, total = 0;
        for (int[] t : boxTypes) {
            if (space == 0) break;
            int take = Math.min(t[0], space);
            total += take * t[1];
            space -= take;
        }
        return total;
    }
}

3Optimal (bucket boxes by units)

TimeO(n + U)One pass to fill buckets and one pass over U = 1000 unit values.
SpaceO(U)The bucket array of size U + 1.

Units per box are at most 1000, so add up the number of boxes for every units value in an array of size 1001. Then walk the units values from 1000 down to 1, loading boxes greedily. No comparison sort is needed.

  1. count[u] += numberOfBoxes for every type with units u.
  2. For u from 1000 down to 1: take = min(count[u], space); add take * u; reduce space; stop at 0.
class Solution {
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        int[] count = new int[1001];
        for (int[] t : boxTypes) count[t[1]] += t[0];
        int space = truckSize, total = 0;
        for (int u = 1000; u >= 1 && space > 0; u--) {
            int take = Math.min(count[u], space);
            total += take * u;
            space -= take;
        }
        return total;
    }
}

Edge cases to test

  • Truck capacity larger than the total number of boxes
  • Truck fills up in the middle of a box type
  • Several types with the same units per box

Hints

Hint 1

Every box takes one slot, so a slot is always best used by the box with the most units.

Hint 2

Process box types from most to fewest units per box, taking as many boxes as still fit.

Hint 3

Units per box are at most 1000, so you can bucket the boxes by units instead of sorting.

FAQ

What is the best time complexity for Maximum Units on a Truck?

Optimal (bucket boxes by units) runs in O(n + U) time and O(U) extra space. One pass to fill buckets and one pass over U = 1000 unit values.

Which pattern does Maximum Units on a Truck use?

It is a arrays & hashing problem that uses the greedy pattern. Other problems with the same pattern: Integer to Roman, Jump Game II, Jump Game.

Is there a brute force solution for Maximum Units on a Truck?

Yes. Brute force (repeatedly pick the best remaining type) takes O(n²) time and O(n) space. While the truck has room, scan all box types for the one with the most units per box that still has boxes, load as many of it as fit, and mark it used.

Which edge cases should I test for Maximum Units on a Truck?

Truck capacity larger than the total number of boxes; Truck fills up in the middle of a box type; Several types with the same units per box.