# Leetcode – Maximum Units on a Truck Solution

The “Maximum Units on a Truck” problem is a classic example of a greedy algorithm problem and appears on Leetcode as a part of the array challenges. The problem revolves around selecting box types with units of products in a way that maximizes the total number of units that can be accommodated in a truck with limited space. In this extensive guide, we will explore multiple approaches to solving this problem, discuss their time and space complexities, and delve into some corner cases to consider.

## Problem Statement

You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]:

• numberOfBoxesi is the number of boxes of type i.
• numberOfUnitsPerBoxi 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 cannot put more than one box of the same type on the truck.

Write a function to return the maximum total number of units that can be put on the truck.

#### Example:

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

## Basic Greedy Approach: Sorting and Selecting

A simple approach to solving this problem involves sorting the array of box types based on the number of units per box in descending order. Then, we can iteratively pick as many boxes as the truck can carry.

#### Python Code for Basic Greedy Approach

def maximumUnits(boxTypes, truckSize):
# Sort the box types by the number of units per box in descending order
boxTypes.sort(key=lambda x: x[1], reverse=True)

total_units = 0
for boxes, units in boxTypes:
if truckSize == 0:
break
# Calculate how many boxes of this type can be carried
boxes_to_carry = min(boxes, truckSize)
total_units += boxes_to_carry * units
truckSize -= boxes_to_carry

return total_units

### Time Complexity

The time complexity of this approach is O(n logā” n), primarily due to sorting, where n is the number of different box types.

## Testing the Solution

Before submitting your solution on Leetcode, it’s good practice to run it against some test cases.

assert maximumUnits([[1, 3], [2, 2], [3, 1]], 4) == 8
assert maximumUnits([[5, 10], [2, 5], [4, 7], [3, 9]], 10) == 91