Leetcode – Maximum Units on a Truck Solution

Spread the love

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

Additional Optimizations

The basic greedy algorithm is quite efficient for this problem. However, one could consider using a priority queue to keep track of the units if the input list becomes too large or if you need to maintain additional information about the boxes. The use of a priority queue can make the code more modular and extendable for similar kinds of problems.

Conclusion

The “Maximum Units on a Truck” problem serves as a fundamental introduction to greedy algorithms. It’s essential to understand that greedy solutions don’t always work for every problem but are often the most straightforward and efficient ways to solve specific types of challenges. The core idea here is to make the locally optimal choice at each stage (i.e., always picking the boxes with the most units that can fit on the truck).

Leave a Reply