Maximum Units on a Truck

Easy
345.

Maximum Units on a Truck

Maximum Units on a Truck is an easy coding problem on arrays, sorting and greedy, asked in Amazon and Adobe interviews.

You are loading boxes onto one truck. boxTypes[i] = [count, unitsPerBox] means there are count boxes of that type and each holds unitsPerBox units.

You may load at most truckSize boxes in total, choosing any combination. Return the maximum total number of units you can carry.

Example 1

Input
boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
Output
8
Explanation
Take the 1 box of 3 units, both boxes of 2 units, and one box of 1 unit.

Example 2

Input
boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
Output
91

Example 3

Input
boxTypes = [[1,1]], truckSize = 5
Output
1

Constraints

  • 1 <= boxTypes.length <= 30
  • 1 <= count, unitsPerBox <= 1000
  • 1 <= truckSize <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} boxTypes
 * @param {number} truckSize
 * @return {number}
 */
var maximumUnits = function(boxTypes, truckSize) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Units on a Truck — Solution in Python, Java & C++

Maximum Units on a Truck solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Maximum Units on a Truck is an easy coding problem on arrays, sorting and greedy, asked in Amazon and Adobe interviews.

  • Difficulty: Easy
  • Topics: Arrays, Sorting, Greedy
  • Asked at: Amazon, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are loading boxes onto one truck. boxTypes[i] = [count, unitsPerBox] means there are count boxes of that type and each holds unitsPerBox units.

You may load at most truckSize boxes in total, choosing any combination. Return the maximum total number of units you can carry.

Example 1

Input: boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
Output: 8
Explanation: Take the 1 box of 3 units, both boxes of 2 units, and one box of 1 unit.

Example 2

Input: boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
Output: 91

Example 3

Input: boxTypes = [[1,1]], truckSize = 5
Output: 1

Constraints

  • 1 <= boxTypes.length <= 30
  • 1 <= count, unitsPerBox <= 1000
  • 1 <= truckSize <= 1000

Hints for Maximum Units on a Truck

  1. Hint 1

    Every box takes the same amount of truck space, so always prefer the box that carries more units.

  2. Hint 2

    Sort by units per box descending and take greedily until the truck is full.

  3. Hint 3

    The last box type may be taken only partially — clamp the count to the remaining space.

How to solve Maximum Units on a Truck

Every box occupies one slot, so fill the truck with the highest-units boxes first.

Approach

  1. Sort box types by units per box descending.
  2. For each type, take min(remaining, count) boxes and add their units; stop when the truck is full.

Why it works

Replacing any loaded box with an unloaded box of higher units never reduces the total, so the greedy order is optimal (a fractional knapsack with unit weights).

Complexity

  • Time — O(n log n)
  • Space — O(1) beyond the sort

Pitfalls

  • The last type may be taken partially — clamp to the remaining slots.

Reference solution

Python

def maximumUnits(boxTypes, truckSize: int) -> int:
    ordered = sorted(boxTypes, key=lambda b: -b[1])
    remaining = truckSize
    total = 0
    for count, units in ordered:
        if remaining <= 0:
            break
        take = min(remaining, count)
        total += take * units
        remaining -= take
    return total

Java

public static int maximumUnits(int[][] boxTypes, int truckSize) {
    int[][] s = boxTypes.clone();
    Arrays.sort(s, (a, b) -> b[1] - a[1]);
    int remaining = truckSize, total = 0;
    for (int i = 0; i < s.length && remaining > 0; i++) {
        int take = Math.min(remaining, s[i][0]);
        total += take * s[i][1];
        remaining -= take;
    }
    return total;
}

C++

int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
    vector<vector<int>> s = boxTypes;
    sort(s.begin(), s.end(), [](const vector<int>& a, const vector<int>& b) { return a[1] > b[1]; });
    int remaining = truckSize, total = 0;
    for (int i = 0; i < (int) s.size() && remaining > 0; i++) {
        int take = min(remaining, s[i][0]);
        total += take * s[i][1];
        remaining -= take;
    }
    return total;
}

JavaScript

var maximumUnits = function(boxTypes, truckSize) {
    const sorted = boxTypes.slice().sort(function(a, b) { return b[1] - a[1]; });
    let remaining = truckSize, total = 0;
    for (let i = 0; i < sorted.length && remaining > 0; i++) {
        const take = Math.min(remaining, sorted[i][0]);
        total += take * sorted[i][1];
        remaining -= take;
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms