Problem Description

You need to load boxes onto a truck to maximize the total number of units transported. You're given a 2D array boxTypes where each element boxTypes[i] = [numberOfBoxes_i, numberOfUnitsPerBox_i] contains:

• numberOfBoxes_i: the available quantity of boxes of type i
• numberOfUnitsPerBox_i: the number of units contained in each box of type i

You also have a truckSize parameter that represents the maximum number of boxes the truck can carry.

Your task is to select boxes to load onto the truck such that:

1. The total number of boxes doesn't exceed truckSize
2. The total number of units on the truck is maximized

You can choose any combination of available boxes from different types as long as you don't exceed the truck's capacity.

For example, if you have boxTypes = [[1,3],[2,2],[3,1]] and truckSize = 4:

• Type 1: 1 box with 3 units each
• Type 2: 2 boxes with 2 units each
• Type 3: 3 boxes with 1 unit each

The optimal strategy would be to take 1 box of type 1 (3 units) and 2 boxes of type 2 (4 units), plus 1 box of type 3 (1 unit), giving you 4 boxes total with 8 units.

The solution uses a greedy approach by sorting the box types by units per box in descending order, then filling the truck with boxes that have the most units first until the truck is full or all boxes are loaded.

Intuition

The key insight is that we want to maximize the total units while being constrained by the number of boxes we can carry. Since each box takes up exactly one slot on the truck regardless of how many units it contains, we should prioritize boxes with the highest unit density (units per box).

Think of it like packing for a trip with limited luggage space - you'd want to pack the most valuable items first. Here, "value" is the number of units each box contains.

This naturally leads to a greedy strategy: always pick the boxes with the most units first. If we have boxes with 5 units each and boxes with 1 unit each, and we can only carry a limited number of boxes, we'd obviously want to fill our truck with the 5-unit boxes before considering the 1-unit boxes.

The approach becomes clear:

1. Sort all box types by their units per box in descending order (highest units first)
2. Greedily take as many boxes as possible from each type, starting with the highest-value boxes
3. Keep track of remaining truck capacity as we load boxes
4. Stop when either the truck is full or we've considered all available boxes

For each box type, we take min(truckSize, numberOfBoxes) - either all available boxes of that type or just enough to fill the remaining truck space, whichever is smaller. This ensures we maximize units while respecting both the truck's capacity and the available inventory.

The formula ans += unitsPerBox * min(truckSize, numberOfBoxes) captures this perfectly - we add the total units from the boxes we can actually load.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation follows a greedy algorithm with sorting:

Step 1: Sort the boxes by unit value

sorted(boxTypes, key=lambda x: -x[1])

We sort boxTypes in descending order based on the number of units per box (second element of each subarray). The negative sign -x[1] ensures descending order - boxes with the most units come first.

Step 2: Greedily load boxes onto the truck

for a, b in sorted(boxTypes, key=lambda x: -x[1]):
    ans += b * min(truckSize, a)
    truckSize -= a
    if truckSize <= 0:
        break

For each box type [a, b] where:

• a = number of available boxes of this type
• b = units per box of this type

We iterate through the sorted list and:

1. Calculate units to add: b * min(truckSize, a)

   • If we have more boxes available (a) than remaining truck capacity (truckSize), we can only take truckSize boxes
   • Otherwise, we take all a available boxes
   • Multiply the number of boxes taken by units per box (b) to get total units

2. Update remaining capacity: truckSize -= a

   • Subtract the number of boxes of this type from remaining capacity
   • Note: truckSize can become negative, but we handle this in the next step

3. Check termination condition: if truckSize <= 0: break

   • If truck is full or overfilled, stop processing
   • When truckSize becomes 0 or negative, we've used all available space

The algorithm ensures optimal selection by always choosing the most valuable boxes first, and the min() function handles the edge case where we might not need all boxes of a particular type to fill the truck.

Time Complexity: O(n log n) for sorting, where n is the number of box types Space Complexity: O(1) if we don't count the sorted array (or O(n) if we do)

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

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

Step 1: Sort by units per box (descending)

Original array with annotations:

• [5,10] → 5 boxes with 10 units each
• [2,5] → 2 boxes with 5 units each
• [4,7] → 4 boxes with 7 units each
• [3,9] → 3 boxes with 9 units each

After sorting by units per box (second element, descending):

[[5,10], [3,9], [4,7], [2,5]]

Step 2: Greedily load boxes

Initialize: ans = 0, truckSize = 10

Iteration 1: [5,10] (5 boxes, 10 units each)

• Can take: min(truckSize=10, boxes=5) = 5 boxes
• Add units: ans += 10 * 5 = 50
• Update capacity: truckSize = 10 - 5 = 5
• Continue (truck not full)

Iteration 2: [3,9] (3 boxes, 9 units each)

• Can take: min(truckSize=5, boxes=3) = 3 boxes
• Add units: ans += 9 * 3 = 27 (total: 77)
• Update capacity: truckSize = 5 - 3 = 2
• Continue (truck not full)

Iteration 3: [4,7] (4 boxes, 7 units each)

• Can take: min(truckSize=2, boxes=4) = 2 boxes
• Add units: ans += 7 * 2 = 14 (total: 91)
• Update capacity: truckSize = 2 - 4 = -2
• Stop (truckSize ≤ 0)

Result: Maximum units = 91

We loaded:

• 5 boxes with 10 units each = 50 units
• 3 boxes with 9 units each = 27 units
• 2 boxes with 7 units each = 14 units
• Total: 10 boxes carrying 91 units

By prioritizing high-value boxes first, we maximized the total units within the truck's 10-box capacity.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n), where n is the length of the array boxTypes. The dominant operation is the sorting of the boxTypes array using sorted(), which takes O(n × log n) time. After sorting, the code iterates through the sorted array once, which takes O(n) time. Since O(n × log n) + O(n) = O(n × log n), the overall time complexity is O(n × log n).

Space Complexity: O(n), where n is the length of the array boxTypes. The sorted() function in Python creates a new sorted list rather than sorting in-place, which requires O(n) additional space to store the sorted copy of the input array. The other variables (ans, a, b, truckSize) use constant space O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly updating truck capacity

A common mistake is subtracting the wrong value from truckSize. Some developers accidentally subtract num_boxes instead of boxes_to_take:

Incorrect:

for num_boxes, units_per_box in sorted_boxes:
    boxes_to_take = min(truckSize, num_boxes)
    total_units += units_per_box * boxes_to_take
    truckSize -= num_boxes  # Wrong! This subtracts all available boxes
    if truckSize <= 0:
        break

Correct:

for num_boxes, units_per_box in sorted_boxes:
    boxes_to_take = min(truckSize, num_boxes)
    total_units += units_per_box * boxes_to_take
    truckSize -= boxes_to_take  # Correct: subtract only what we took
    if truckSize <= 0:
        break

2. Sorting in the wrong order

Another pitfall is sorting in ascending order instead of descending order, which would load the least valuable boxes first:

Incorrect:

sorted_boxes = sorted(boxTypes, key=lambda box: box[1])  # Ascending order

Correct:

sorted_boxes = sorted(boxTypes, key=lambda box: -box[1])  # Descending order
# OR
sorted_boxes = sorted(boxTypes, key=lambda box: box[1], reverse=True)

3. Off-by-one error in termination condition

Using truckSize < 0 instead of truckSize <= 0 can cause unnecessary iterations:

Inefficient:

if truckSize < 0:  # Continues even when truckSize is exactly 0
    break

Efficient:

if truckSize <= 0:  # Stops immediately when truck is full
    break

4. Not handling the partial box case correctly

Forgetting to use min() when calculating boxes to take can lead to counting more boxes than actually fit:

Incorrect:

total_units += units_per_box * num_boxes  # Always takes all available boxes

Correct:

boxes_to_take = min(truckSize, num_boxes)
total_units += units_per_box * boxes_to_take  # Takes only what fits