Log inSign up
easyLeetCodeNot Started

Maximum Units on a Truck

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Greedy
Solve on LeetCode
Lesson

Problem Statement

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 pack on the truck as long as the total number of boxes does not exceed truckSize.

Return the maximum total number of units that can be put on the truck.

Example 1 · Example 1: Partial Packing:

Input: boxTypes = [[1, 3], [2, 2], [3, 1]], truckSize = 4
Output: 8
Explanation: - 1 box of type 0 (3 units): 1 box, 3 units. Remaining size = 3.\n- 2 boxes of type 1 (2 units): 2 boxes, 4 units. Remaining size = 1.\n- 1 box of type 2 (1 unit): 1 box, 1 unit. Remaining size = 0.\nTotal units = 3 + 4 + 1 = 8.

Example 2 · Example 2: Large Truck Size:

Input: boxTypes = [[5, 10], [2, 5], [4, 7], [3, 9]], truckSize = 10
Output: 91
Explanation: Sorted by units: [5, 10], [3, 9], [4, 7], [2, 5].\nTake 5 boxes of 10 units = 50 units (5 left).\nTake 3 boxes of 9 units = 27 units (2 left).\nTake 2 boxes of 7 units = 14 units (0 left).\nTotal units = 50 + 27 + 14 = 91.

Constraints:

  • 1 <= boxTypes.length <= 1000
  • 1 <= numberOfBoxes_i, numberOfUnitsPerBox_i <= 1000
  • 1 <= truckSize <= 106

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why uniform item weights make greedy choice strictly optimal without fractions.
  • Recognize the parallel with fractional knapsack.
  • Implement the greedy solution across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Knapsack problem where each item has identical size (1 box).
  • Greedy choice property trivially holds because size is uniform.
  • Maximize total value under capacity constraint.

Algorithmic Decision Tree:

  • Sort by unitsPerBox descending.
  • Greedily pack maximum boxes from top unit density.

Connected Patterns:

Fractional KnapsackMaximum Bags With Full Capacity of RocksBag of Tokens

1. Recursive Knapsack Search

Intuition

Recursively branch on how many boxes of each type to take (from 0 up to min(truckSize, boxes)), searching for the maximum total units.

Algorithm

  1. Step 1: Define recursive function solve(idx, remainingCapacity).
  2. Step 2: If idx == n or remainingCapacity == 0, return 0.
  3. Step 3: Try choosing k boxes where 0 <= k <= min(remainingCapacity, boxTypes[idx][0]).
  4. Step 4: Recurse on solve(idx + 1, remainingCapacity - k) + k * boxTypes[idx][1].
  5. Step 5: Return maximum across all choices.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int solve(int idx, int capacity, const vector<vector<int>>& boxTypes) {
9 if (idx == boxTypes.size() || capacity <= 0) return 0;
10 int maxUnits = 0;
11 int maxTake = min(capacity, boxTypes[idx][0]);
12 for (int k = 0; k <= maxTake; ++k) {
13 int current = k * boxTypes[idx][1] + solve(idx + 1, capacity - k, boxTypes);
14 maxUnits = max(maxUnits, current);
15 }
16 return maxUnits;
17 }
18public:
19 int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
20 return solve(0, truckSize, boxTypes);
21 }
22};
23
24int main() {
25 Solution sol;
26 vector<vector<int>> boxTypes = {{1, 3}, {2, 2}, {3, 1}};
27 int truckSize = 4;
28 cout << "Max Units: " << sol.maximumUnits(boxTypes, truckSize) << endl;
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(2^N)
  • Space complexity: O(N)

2. Max-Heap / Priority Queue

Intuition

Insert all box types into a max-heap keyed by units per box. Repeatedly pop the highest unit box type until the truck is full.

Algorithm

  1. Step 1: Insert all boxTypes [count, units] into a max-heap prioritizing units per box.
  2. Step 2: Initialize totalUnits = 0.
  3. Step 3: While heap is non-empty and truckSize > 0:
  4. Step 4: Extract the top element [count, units].
  5. Step 5: take = min(truckSize, count). Add take * units to totalUnits, truckSize -= take.
  6. Step 6: Return totalUnits.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5using namespace std;
6
7class Solution {
8public:
9 int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
10 auto cmp = [](const vector<int>& a, const vector<int>& b) {
11 return a[1] < b[1];
12 };
13 priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> maxHeap(cmp);
14
15 for (const auto& box : boxTypes) {
16 maxHeap.push(box);
17 }
18
19 int totalUnits = 0;
20 while (!maxHeap.empty() && truckSize > 0) {
21 auto top = maxHeap.top();
22 maxHeap.pop();
23
24 int take = min(truckSize, top[0]);
25 totalUnits += take * top[1];
26 truckSize -= take;
27 }
28
29 return totalUnits;
30 }
31};
32
33int main() {
34 Solution sol;
35 vector<vector<int>> boxTypes = {{1, 3}, {2, 2}, {3, 1}};
36 int truckSize = 4;
37 cout << "Max Units (Heap): " << sol.maximumUnits(boxTypes, truckSize) << endl;
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N log N)
  • Space complexity: O(N)

3. Greedy Sorting by Units Descending

Intuition

Sort boxTypes descending by units per box. Greedily fill the truck with boxes yielding the highest units first.

Algorithm

  1. Step 1: Sort boxTypes in descending order based on units per box (box[1]).
  2. Step 2: Initialize totalUnits = 0.
  3. Step 3: Iterate through each box type [count, units] in sorted boxTypes.
  4. Step 4: Calculate take = min(truckSize, count).
  5. Step 5: Add take * units to totalUnits and subtract take from truckSize.
  6. Step 6: If truckSize reaches 0, break early and return totalUnits.

Interactive Trace for Maximum Units on a Truck

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Inspect box type [1, 3]
Visual state
Values and pointers at this exact step
pointers
S
taken 1
pending
pending
0
↑ current
1
2
Check / comparison
take = min(4, 1) = 1 box
Decision / next transition
Add 1 * 3 = 3 units. truckSize remaining = 3.
Why this step matters

Step 1: Inspect box type [1, 3]. truckSize = 4 >= 1 box. Take 1 box.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
10 sort(boxTypes.begin(), boxTypes.end(), [](const vector<int>& a, const vector<int>& b) {
11 return a[1] > b[1];
12 });
13
14 int totalUnits = 0;
15 for (const auto& box : boxTypes) {
16 int take = min(truckSize, box[0]);
17 totalUnits += take * box[1];
18 truckSize -= take;
19 if (truckSize == 0) break;
20 }
21
22 return totalUnits;
23 }
24};
25
26int main() {
27 Solution sol;
28 vector<vector<int>> boxTypes = {{1, 3}, {2, 2}, {3, 1}};
29 int truckSize = 4;
30 cout << "Max Units (Optimal): " << sol.maximumUnits(boxTypes, truckSize) << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(N log N)
  • Space complexity: O(1) auxiliary

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Recursive BacktrackingO(2^N)O(N)Recursively try choosing between taking available boxes of the current type and advancing to subsequent types.Recursive combinatorial explosion.
2.Better — Max-Heap / Priority QueueO(N log N)O(N)Push all box types into a max-heap ordered by units per box. Repeatedly pop the highest unit box type and fill remaining truck capacity.Heap insertion and extraction.
3.Optimal — Greedy Sorting by Units DescendingOptimalO(N log N)O(1) auxiliarySort boxTypes descending by units per box. Iterate and take min(truckSize, numBoxes) of each type, updating units and remaining truck capacity.Sorting operation.
Back to DSA Sheet