Maximum Units on a Truck - Solution & Explanation

Problem Overview: You are given different box types where each type contains a number of boxes and a number of units per box. A truck can carry at most truckSize boxes. The goal is to load boxes so the total units on the truck is maximized.

Approach 1: Greedy Approach using Sorting (Time: O(n log n), Space: O(1) or O(n) depending on sorting implementation)

This problem fits the greedy pattern. Each box type has a "value" (units per box). To maximize total units, always load boxes that give the highest units first. Start by sorting the box types in descending order by unitsPerBox using a sorting algorithm. Then iterate through the sorted list and take as many boxes as possible from each type until the truck reaches its capacity.

For each box type, compute boxesTaken = min(numberOfBoxes, remainingTruckCapacity). Multiply that by unitsPerBox and add it to the total. Decrease the remaining capacity and continue. The key insight is that a locally optimal choice (highest units per box first) leads to the global optimum because each box contributes independently to the final total.

This approach is simple and reliable. Sorting dominates the runtime with O(n log n), where n is the number of box types. The rest of the algorithm is a single pass over the array. Space complexity is O(1) if the sort is in-place. The input structure is just an array of box types.

Approach 2: Counting Sort Based Approach (Time: O(n + k), Space: O(k))

The constraints allow an optimization using counting sort. Instead of sorting box types directly, group them by unitsPerBox. Since the maximum units per box is bounded (commonly ≤1000 in the problem constraints), create a frequency structure where each index represents a specific units value.

Iterate through the input and accumulate how many boxes exist for each unitsPerBox value. Then traverse this structure from the highest unit value down to the lowest. At each step, greedily load as many boxes as possible until the truck is full.

This avoids the O(n log n) sorting step. Building the counts takes O(n), and scanning the bucket array takes O(k), where k is the maximum possible units per box. The approach uses O(k) additional space but improves runtime when n is large and the unit range is small.

Recommended for interviews: The greedy sorting solution is what most interviewers expect first. It clearly demonstrates recognition of the greedy pattern and is easy to implement under time pressure. The counting sort optimization shows deeper understanding of constraints and can improve performance when the unit range is limited.