Maximum Units on a Truck - Practice Coding Problems

Maximum Units on a Truck - Problem

You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxes_i, numberOfUnitsPerBox_i]:

numberOfBoxes_i is the number of boxes of type i.
numberOfUnitsPerBox_i is the number of units in each box of the 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.

Input & Output

Example 1 — Basic Case

$ Input: boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4

› Output: 8

💡 Note: Take 1 box of type 1 (3 units), 2 boxes of type 2 (4 units), and 1 box of type 3 (1 unit). Total = 3 + 4 + 1 = 8 units.

Example 2 — Limited Capacity

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

› Output: 91

💡 Note: Sort by units per box: [5,10], [3,9], [4,7], [2,5]. Take 5 boxes (50 units) + 3 boxes (27 units) + 2 boxes (14 units) = 91 units.

Example 3 — Single Type

$ Input: boxTypes = [[1,1]], truckSize = 1

› Output: 1

💡 Note: Only one box type available, take 1 box with 1 unit.

Constraints

1 ≤ boxTypes.length ≤ 1000
1 ≤ numberOfBoxes_i, numberOfUnitsPerBox_i ≤ 1000
1 ≤ truckSize ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Box types with [count, units] and truck capacity

Greedy Strategy

Sort by units per box and select highest value first

Output

Maximum total units that can fit

Key Takeaway

🎯 Key Insight: Sort by units per box and greedily select highest value boxes first

Asked in

a Amazon 25 A Apple 15 M Microsoft 10

The key insight is that we should prioritize boxes with the highest units per box to maximize total units. The optimal approach is to sort box types by units per box in descending order and use a greedy strategy to fill the truck. Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(2ⁿ)	O(n)	Generate all possible combinations of boxes and find the one with maximum units
Greedy Approach - Sort by Units per Box	O(n log n)	O(1)	Sort box types by units per box in descending order and pick greedily

Brute Force - Try All Combinations — Algorithm Steps

Generate all possible combinations of box selections
For each valid combination (≤ truckSize boxes), calculate total units
Return the maximum units found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Combinations

Create all possible subsets of box types

Check Validity

Ensure total boxes ≤ truck capacity

Find Maximum

Track combination with highest units

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int** boxTypes, int boxTypesSize, int truckSize) {
    int maxUnits = 0;
    
    // Try all possible combinations
    for (int mask = 0; mask < (1 << boxTypesSize); mask++) {
        int totalBoxes = 0;
        int totalUnits = 0;
        
        for (int i = 0; i < boxTypesSize; i++) {
            if (mask & (1 << i)) {
                int boxes = boxTypes[i][0];
                int units = boxTypes[i][1];
                if (totalBoxes + boxes <= truckSize) {
                    totalBoxes += boxes;
                    totalUnits += boxes * units;
                } else {
                    int remaining = truckSize - totalBoxes;
                    totalUnits += remaining * units;
                    totalBoxes = truckSize;
                    break;
                }
            }
        }
        
        if (totalBoxes <= truckSize) {
            if (totalUnits > maxUnits) {
                maxUnits = totalUnits;
            }
        }
    }
    
    return maxUnits;
}

int main() {
    // Simple parsing for demo - read as [[1,3],[2,2],[3,1]] format
    int boxTypes[3][2] = {{1,3}, {2,2}, {3,1}};
    int* boxTypesPtr[3] = {boxTypes[0], boxTypes[1], boxTypes[2]};
    int truckSize = 4;
    
    printf("%d\n", solution(boxTypesPtr, 3, truckSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ)

We try all possible subsets of box types, which is exponential

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth for generating combinations

⚡ Linearithmic Space

25.0K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler