Domain 1EasyCORE

Maximum Units on a Truck

The problem requires us to maximize the number of units that can be loaded onto a truck given a set of box types and their respective unit counts. The input consists of a 2D array `boxTypes`, where each element is an array containing two integers: the first integer represents the number of boxes of a certain type, and the second integer represents the number of units in each box of that type. Additionally, we are given an integer `truckSize` which indicates the maximum number of boxes that can be loaded onto the truck.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Greedy#Sort

1710. Maximum Units on a Truck

Model: qwen2.5-coder:14b
Topics: Greedy,Sort
FAANG asked: 1
Acceptance rate: 69.9%


Problem Breakdown

The problem requires us to maximize the number of units that can be loaded onto a truck given a set of box types and their respective unit counts. The input consists of a 2D array boxTypes, where each element is an array containing two integers: the first integer represents the number of boxes of a certain type, and the second integer represents the number of units in each box of that type. Additionally, we are given an integer truckSize which indicates the maximum number of boxes that can be loaded onto the truck.

Inputs:

  • boxTypes: A 2D array where each element is [numberOfBoxesi, numberOfUnitsPerBoxi].
  • truckSize: An integer representing the maximum number of boxes that can be loaded onto the truck.

Outputs:

  • The maximum total number of units that can be loaded onto the truck.

Implicit Constraints or Edge Cases:

  • If boxTypes is empty, the output should be 0.
  • If truckSize is 0, the output should be 0 regardless of the contents of boxTypes.
  • Each box type has a positive number of boxes and units.

Intuition

A brute-force approach would involve checking all possible combinations of box types to see which combination yields the maximum number of units. However, this approach is computationally expensive with a time complexity of O(2^n), where n is the number of different box types, making it infeasible for larger inputs.

The key insight here is to prioritize loading boxes that contain more units per box first. This greedy strategy ensures that we maximize the total number of units loaded onto the truck without exceeding the truckSize. By sorting the box types based on the number of units per box in descending order, we can iteratively load as many boxes as possible from each type until the truck is full.

Approach

  1. Sort the Box Types: Sort the boxTypes array in descending order based on the number of units per box.
  2. Initialize Variables: Initialize a variable total_units to keep track of the total number of units loaded onto the truck and a variable remaining_boxes to keep track of the remaining capacity of the truck (truckSize).
  3. Iterate Through Box Types: For each box type in the sorted array:
    • Determine the number of boxes that can be loaded from this type, which is the minimum of the remaining capacity of the truck and the number of boxes available for this type.
    • Add the units from these boxes to total_units.
    • Decrease the remaining_boxes by the number of boxes loaded.
    • If remaining_boxes becomes 0, break out of the loop as the truck is full.
  4. Return Result: Return the total_units.

Complexity Analysis

  • Time Complexity: O(n log n) due to the sorting step, where n is the number of different box types. The subsequent iteration through the sorted array takes linear time, O(n).
  • Space Complexity: O(1) as we are using a constant amount of extra space.

Solution

def maximumUnits(boxTypes, truckSize):
    # Sort box types by units per box in descending order
    boxTypes.sort(key=lambda x: x[1], reverse=True)
    
    total_units = 0
    remaining_boxes = truckSize
    
    for numberOfBoxes, unitsPerBox in boxTypes:
        if remaining_boxes == 0:
            break
        
        # Load as many boxes as possible from this type
        boxes_to_load = min(remaining_boxes, numberOfBoxes)
        total_units += boxes_to_load * unitsPerBox
        remaining_boxes -= boxes_to_load
    
    return total_units

Edge Cases Handled

  • Empty boxTypes: The function returns 0 as there are no boxes to load.
  • truckSize is 0: The function immediately returns 0 without processing any box types.
  • All box types have the same number of units per box: The function correctly loads as many boxes as possible based on truckSize.
  • Mixed box types with varying units per box: The function prioritizes loading boxes with higher units first, ensuring the maximum total units are loaded.