Interview Prepgreedy-algorithmseasyAmazonGoogle

Maximum Units on a Truck

Choose your preparation mode4 modes available

Try It Solution Trace

Start learning this pattern below

Jump into concepts and practice - no test required

Recommended

Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong

📋

Problem

Imagine you are a truck driver who needs to maximize the number of units loaded onto your truck from different box types, each with a limited number of boxes and units per box.

You are assigned to put some number of boxes onto a truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxes_i, numberOfUnitsPerBox_i]: - numberOfBoxes_i is the number of boxes of type i. - numberOfUnitsPerBox_i 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. Return the maximum total number of units that can be put on the truck.

1 ≤ boxTypes.length ≤ 10^51 ≤ numberOfBoxes_i, numberOfUnitsPerBox_i ≤ 10^51 ≤ truckSize ≤ 10^9

Edge cases: truckSize is zero → output 0Only one box type with boxes less than truckSize → output all units from that typeMultiple box types with same units per box → pick any order but total units same

</>

IDE

def maximumUnits(boxTypes: list[list[int]], truckSize: int) -> int:

def maximumUnits(boxTypes, truckSize):
    # Write your solution here
    pass

class Solution {
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
    // Write your solution here
    return 0;
}

function maximumUnits(boxTypes, truckSize) {
    // Write your solution here
}

0/9

Common Bugs to Avoid

Wrong: 0Not handling empty input or zero truckSize correctly, returning zero always.✅ Add condition to return 0 only when truckSize is zero or boxTypes is empty, otherwise proceed.

Wrong: sum of all units without sortingNot sorting boxTypes by units per box descending, picking boxes in input order.✅ Sort boxTypes by units per box descending before picking boxes greedily.

Wrong: units assuming unlimited boxesTreating problem as unbounded knapsack, ignoring box count limits.✅ Limit boxes picked to min(numberOfBoxes, remaining truckSize) for each box type.

Wrong: incorrect units due to off-by-one in truckSize decrementLoop or decrement logic off by one, picking wrong number of boxes.✅ Ensure truckSize decrements correctly after picking boxes and loop conditions are accurate.

Wrong: TLE or timeoutUsing brute force exponential approach instead of sorting + greedy.✅ Implement sorting by units descending and greedy picking to achieve O(n log n) complexity.

✓

Test Cases

t1_01basic

Input{"boxTypes":[[1,3],[2,2],[3,1]],"truckSize":4}

Expected8

Pick 1 box of type 0 (3 units) and 2 boxes of type 1 (2 units each) and 1 box of type 2 (1 unit). Total units = 3 + 4 + 1 = 8.

t1_02basic

Input{"boxTypes":[[5,10],[2,5],[4,7]],"truckSize":6}

Expected57

Pick 5 boxes of type 0 (10 units each) and 1 box of type 2 (7 units). Total units = 50 + 7 = 57.

Practice

(1/5)

1. You are given a list of non-negative integers and need to arrange them to form the largest possible number when concatenated. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic Programming to find the maximum concatenation by exploring all subsequences

B. Sorting the numbers as strings using a custom comparator that compares concatenations

C. Greedy approach by always picking the largest integer first

D. Brute force generating all permutations and selecting the maximum concatenation

3. Consider the following Python code snippet implementing the optimal solution to remove k digits from a number string to get the smallest number. What is the output of removeKdigits("1432", 2)?

def removeKdigits(num: str, k: int) -> str:
    builder = []
    for digit in num:
        while k > 0 and builder and builder[-1] > digit:
            builder.pop()
            k -= 1
        builder.append(digit)
    while k > 0:
        builder.pop()
        k -= 1
    result = ''.join(builder).lstrip('0')
    return result if result else '0'

easy

A. "14"

B. "13"

C. "12"

D. "32"

Maximum Units on a Truck

Start learning this pattern below

Practice

Solution

Step 1: Understand the problem requires ordering numbers to maximize concatenation

Step 2: Recognize that sorting with a custom comparator based on concatenation comparisons guarantees optimal order

Final Answer:

Quick Check:

Solution

Step 1: Understand the problem constraints

Step 2: Identify the approach that efficiently fixes digits from right to left

Final Answer:

Quick Check:

Solution

Step 1: Trace builder and k during iteration

Step 2: Remove remaining k and finalize

Final Answer:

Quick Check:

Solution

Step 1: Identify furthest_jump calculation

Step 2: Check impact

Final Answer:

Quick Check:

Solution

Step 1: Identify sorting cost

Step 2: Analyze heap operations

Final Answer:

Quick Check: