Start by sorting box types in descending order of units per box. Then iteratively add boxes to the truck, ensuring the truck size limit is never exceeded. This greedy approach guarantees the maximum total units while maintaining the invariant that adding a higher-unit box is always optimal when space remains.
Problem Statement
You are given a 2D array boxTypes where boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]. Each entry represents a type of box, the number available, and the units contained. Your goal is to load boxes onto a truck to maximize total units.
You also have an integer truckSize indicating the maximum number of boxes that can fit on the truck. You may select any combination of boxes without exceeding this limit. Return the maximum total units that the truck can carry.
Examples
Example 1
Input: boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
Output: 8
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
Example details omitted.
Constraints
- 1 <= boxTypes.length <= 1000
- 1 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000
- 1 <= truckSize <= 106
Solution Approach
Sort Box Types by Units
Sort the boxTypes array in descending order based on numberOfUnitsPerBoxi. This ensures the greedy choice—always picking the box with the most units per box—is straightforward and aligns with the invariant for maximizing units.
Iterative Loading
Traverse the sorted array and add boxes to the truck one type at a time. For each type, add either all available boxes or just enough to reach truckSize, whichever is smaller. Update the total units accumulated during this process.
Early Termination
Stop adding boxes once the truckSize limit is reached. This prevents overfilling and confirms the greedy invariant that no further units can be gained beyond this point.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n log n) due to sorting, where n is the number of box types. Space complexity is O(1) extra space if sorting in place, otherwise O(n). Iteration over box types is linear, O(n).
What Interviewers Usually Probe
- Mentions prioritizing boxes with higher units per box.
- Asks how to handle remaining truck capacity after partial selection of a box type.
- Looks for proof that greedy selection guarantees maximum units.
Common Pitfalls or Variants
Common pitfalls
- Failing to sort by units per box, leading to suboptimal total units.
- Ignoring the truckSize limit when adding boxes, which breaks constraints.
- Adding boxes of a lower-unit type before exhausting higher-unit types.
Follow-up variants
- Maximize total units with multiple trucks each with different capacities.
- Boxes have weights and units; maximize units without exceeding truck weight limit.
- Box types may have expiration or priority constraints affecting loading order.
How GhostInterview Helps
- Highlights the greedy pattern and explains why selecting highest-unit boxes first is optimal.
- Guides through step-by-step iteration with live invariant checks to prevent exceeding truckSize.
- Provides quick identification of edge cases, such as partial selection of a box type.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the core greedy strategy in Maximum Units on a Truck?
Always select boxes with the highest units per box first until the truck is full. This guarantees maximal total units.
Can I use dynamic programming instead of greedy for this problem?
Dynamic programming is unnecessary and less efficient; the greedy approach with sorting suffices to maximize units.
How do I handle remaining capacity if the next box type has more boxes than space left?
Take only as many boxes as fit in the remaining truck capacity and stop when full.
Does the order of boxTypes in the input affect the solution?
No, sorting by units per box ensures the greedy selection works regardless of initial order.
What pattern does this problem illustrate for interviews?
It demonstrates 'Greedy choice plus invariant validation', highlighting decision-making that always maximizes immediate gain while maintaining constraints.
Need direct help with Maximum Units on a Truck instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Maximum Units on a Truck from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Rearrange columns of a binary matrix to find the largest submatrix of 1s.
Open problem page#1686 Stone Game VIDetermine the winner in Stone Game VI using a greedy strategy that accounts for each stone's dual value impact on Alice and Bob.
Open problem page#1665 Minimum Initial Energy to Finish TasksDetermine the minimum initial energy needed to finish all tasks using a greedy ordering based on required versus actual energy.
Open problem page