Maximum Units on a Truck

▶

Steps

setup

Start with unsorted boxTypes

The algorithm begins with the original boxTypes array and the truckSize available.

💡 Seeing the initial input helps understand the starting point before sorting.

Line:

boxTypes = [[1,3],[2,2],[3,1]]
truckSize = 4

💡 Initial data setup is crucial before any processing.

setup

Sort boxTypes by units per box descending

The boxTypes array is sorted so that box types with the highest units per box come first.

💡 Sorting ensures the greedy approach picks the most valuable boxes first.

Line:

boxTypes.sort(key=lambda x: x[1], reverse=True)

💡 Sorting by units per box is the key greedy step.

setup

Initialize totalUnits to 0

Set totalUnits to zero before starting to pick boxes.

💡 This variable will accumulate the total units loaded onto the truck.

Line:

totalUnits = 0

💡 Starting with zero total units is necessary for accumulation.

traverse

Start iterating over boxTypes with i=0

Begin processing the first box type with 1 box and 3 units each.

💡 The pointer i shows which box type is currently being considered.

Line:

for boxes, units in boxTypes:
    if truckSize == 0:
        break

💡 Iteration starts from the highest units per box type.

insert

Calculate how many boxes to take from boxType 0

Calculate take = min(boxes=1, truckSize=4) = 1 to pick all boxes of this type.

💡 We pick as many boxes as possible without exceeding truck capacity.

Line:

take = min(boxes, truckSize)

💡 Taking the full amount of this box type maximizes units early.

insert

Add units from boxType 0 to totalUnits

Add take * units = 1 * 3 = 3 units to totalUnits, updating totalUnits to 3.

💡 Accumulating units as boxes are loaded is the core calculation.

Line:

totalUnits += take * units

💡 Units accumulate incrementally as boxes are chosen.

shrink

Reduce truckSize by boxes taken from boxType 0

Decrease truckSize by take = 1, updating truckSize from 4 to 3.

💡 Truck capacity decreases as boxes are loaded, limiting future picks.

Line:

truckSize -= take

💡 Tracking remaining capacity is essential for stopping early.

traverse

Move to next boxType i=1

Advance pointer i to the second box type with 2 boxes and 2 units each.

💡 Moving pointer shows progression through sorted box types.

Line:

for boxes, units in boxTypes:

💡 Each box type is processed in order of units per box.

insert

Calculate boxes to take from boxType 1

Calculate take = min(boxes=2, truckSize=3) = 2 to take all boxes of this type.

💡 We take as many boxes as possible without exceeding remaining capacity.

Line:

take = min(boxes, truckSize)

💡 Partial or full box type selection depends on remaining capacity.

insert

Add units from boxType 1 to totalUnits

Add take * units = 2 * 2 = 4 units to totalUnits, updating totalUnits from 3 to 7.

💡 Units accumulate as boxes are loaded, increasing total units.

Line:

totalUnits += take * units

💡 Incremental addition builds the final answer.

shrink

Reduce truckSize by boxes taken from boxType 1

Decrease truckSize by take = 2, updating truckSize from 3 to 1.

💡 Truck capacity decreases as boxes are loaded, limiting future picks.

Line:

truckSize -= take

💡 Remaining capacity controls how many boxes can be taken next.

traverse

Move to next boxType i=2

Advance pointer i to the third box type with 3 boxes and 1 unit each.

💡 Moving pointer shows progression through sorted box types.

Line:

for boxes, units in boxTypes:

💡 Each box type is processed in order of units per box.

insert

Calculate boxes to take from boxType 2

Calculate take = min(boxes=3, truckSize=1) = 1 to fill remaining truck capacity.

💡 We take only as many boxes as the truck can hold.

Line:

take = min(boxes, truckSize)

💡 Partial selection occurs when capacity is limited.

insert

Add units from boxType 2 to totalUnits

Add take * units = 1 * 1 = 1 unit to totalUnits, updating totalUnits from 7 to 8.

💡 Units accumulate as boxes are loaded, increasing total units.

Line:

totalUnits += take * units

💡 Incremental addition builds the final answer.

shrink

Reduce truckSize by boxes taken from boxType 2

Decrease truckSize by take = 1, updating truckSize from 1 to 0.

💡 Truck capacity decreases as boxes are loaded, limiting future picks.

Line:

truckSize -= take

💡 Truck is now full, so no more boxes can be taken.

prune

Check if truckSize is zero to break early

Since truckSize is zero, the loop breaks early without processing more box types.

💡 Early stopping improves efficiency by avoiding unnecessary work.

Line:

if truckSize == 0:
    break

💡 Early stopping is a key optimization in greedy algorithms.

reconstruct

Return totalUnits as final answer

The algorithm returns totalUnits = 8 as the maximum units that can be loaded onto the truck.

💡 Returning the accumulated total units completes the solution.

Line:

return totalUnits

💡 The final answer is the sum of units from all selected boxes.

def maximumUnits(boxTypes, truckSize):
    boxTypes.sort(key=lambda x: x[1], reverse=True)  # STEP 2
    totalUnits = 0  # STEP 3
    for boxes, units in boxTypes:  # STEP 4
        if truckSize == 0:  # STEP 16
            break
        take = min(boxes, truckSize)  # STEP 5,9,13
        totalUnits += take * units  # STEP 6,10,14
        truckSize -= take  # STEP 7,11,15
    return totalUnits  # STEP 17

if __name__ == '__main__':
    boxTypes = [[1,3],[2,2],[3,1]]
    truckSize = 4
    print(maximumUnits(boxTypes, truckSize))  # Output: 8

📊

Maximum Units on a Truck - Watch the Algorithm Execute, Step by Step

Watching the algorithm step through sorting and greedy selection reveals how early stopping and inline calculations optimize the solution efficiently.

setup

[1,3]

0

[2,2]

1

[3,1]

2

Result: 0

sort

[1,3]

0

[2,2]

1

[3,1]

2

Result: 0

initialize

[1,3]

0

[2,2]

1

[3,1]

2

Result: 0

compare

i

[1,3]

0

[2,2]

1

[3,1]

2

Result: 0

move_right

i

[1,3]

0

[2,2]

1

[3,1]

2

Result: 0

record

i

[1,3]

0

[2,2]

1

[3,1]

2

Result: 3

move_left

i

[1,3]

0

[2,2]

1

[3,1]

2

Result: 3

compare

[1,3]

0

i

[2,2]

1

[3,1]

2

Result: 3

move_right

[1,3]

0

i

[2,2]

1

[3,1]

2

Result: 3

record

[1,3]

0

i

[2,2]

1

[3,1]

2

Result: 7

move_left

[1,3]

0

i

[2,2]

1

[3,1]

2

Result: 7

compare

[1,3]

0

[2,2]

1

i

[3,1]

2

Result: 7

move_right

[1,3]

0

[2,2]

1

i

[3,1]

2

Result: 7

record

[1,3]

0

[2,2]

1

i

[3,1]

2

Result: 8

move_left

[1,3]

0

[2,2]

1

i

[3,1]

2

Result: 8

prune

[1,3]

0

[2,2]

1

i

[3,1]

2

Result: 8

return

[1,3]

0

[2,2]

1

[3,1]

2

Result: 8

Key Takeaways

✓ Sorting box types by units per box descending is the foundation of the greedy approach.

This insight is hard to see from code alone because sorting is a separate step that enables the greedy selection order.

✓ The algorithm picks as many boxes as possible from the highest unit box type before moving on.

Visualizing the pointer moving and capacity shrinking clarifies how the greedy choice is applied stepwise.

✓ Early stopping when truckSize reaches zero avoids unnecessary processing and improves efficiency.

Seeing the break condition in action helps understand the optimization beyond the basic greedy logic.

Practice

1. You are given a list of sticks with different lengths. You want to connect all sticks into one by repeatedly merging any two sticks, paying a cost equal to the sum of their lengths each time. Which algorithmic approach guarantees the minimum total cost to connect all sticks?

easy

A. Dynamic Programming that tries all possible merge sequences to find the minimum cost

B. Greedy algorithm using a min-heap to always merge the two shortest sticks first

C. Sorting the sticks once and merging them in sorted order from smallest to largest

D. Greedy algorithm that merges the two longest sticks first to reduce future costs

Solution

1. Step 1: Understand the problem goal

   The goal is to minimize the total cost of merging sticks, where each merge cost equals the sum of the two sticks merged.

2. Step 2: Identify the optimal strategy

   Merging the two shortest sticks first at each step minimizes incremental cost and leads to the global minimum total cost. This is efficiently done using a min-heap.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Min-heap merges shortest sticks first -> minimal total cost [OK]

Hint: Always merge shortest sticks first for minimal cost [OK]

Common Mistakes:

• Merging longest sticks first thinking it reduces future costs
• Sorting once and merging in order without reordering after merges
• Assuming brute force is needed for minimal cost

2. 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"

Solution

1. Step 1: Trace builder and k during iteration

   Start with builder = [], k=2 - digit='1': builder=['1'], k=2 - digit='4': '4' > '1', append: builder=['1','4'], k=2 - digit='3': '3' < '4', pop '4', k=1; append '3': builder=['1','3'] - digit='2': '2' < '3', pop '3', k=0; append '2': builder=['1','2']

2. Step 2: Remove remaining k and finalize

   k=0, no more pops. Result = '12' after stripping leading zeros.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected smallest number after removing 2 digits [OK]

Hint: Pop larger digits when smaller digit found until k=0 [OK]

Common Mistakes:

• Not popping enough digits when smaller digit appears
• Removing digits from front only
• Forgetting to strip leading zeros

3. The following code attempts to implement the peak-valley approach but contains a subtle bug. Identify the line causing incorrect profit calculation.

def maxProfit(prices):
    i = 0
    profit = 0
    n = len(prices)
    while i < n - 1:
        while i < n - 1 and prices[i] > prices[i + 1]:
            i += 1
        valley = prices[i]
        while i < n - 1 and prices[i] < prices[i + 1]:
            i += 1
        peak = prices[i]
        profit += peak - valley
    return profit

medium

A. Line with 'while i < n - 1 and prices[i] < prices[i + 1]:'

B. Line with 'valley = prices[i]'

C. Line with 'while i < n - 1 and prices[i] > prices[i + 1]:'

D. Line with 'profit += peak - valley'

Solution

1. Step 1: Compare with correct condition

   The correct condition should be prices[i] >= prices[i + 1] to skip equal or descending prices.

2. Step 2: Identify bug impact

   Using strict '>' misses equal prices, causing incorrect valley selection and possibly negative profit.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Changing '>' to '>=' fixes edge cases with flat prices [OK]

Hint: Check comparison operators in loops for off-by-one errors [OK]

Common Mistakes:

• Using strict inequalities causing missed equal prices
• Adding negative differences to profit
• Off-by-one errors causing index out of range

4. Consider the following buggy code for the Gas Station problem. Which line contains the subtle bug that can cause incorrect results?

def canCompleteCircuit(gas, cost):
    n = len(gas)
    net = [gas[i] - cost[i] for i in range(n)]
    # Bug: missing total gas check
    prefix = [0] * (2 * n + 1)
    for i in range(2 * n):
        prefix[i+1] = prefix[i] + net[i % n]
    for i in range(n):
        if prefix[i+n] - prefix[i] >= 0:
            return i
    return -1

medium

A. Line 3: net array computation

B. Line 4: missing total gas vs total cost check

C. Line 6: prefix sums computation loop

D. Line 8: checking prefix sums for valid start

Solution

1. Step 1: Identify missing total gas check

   The code does not check if sum(net) < 0 before proceeding, which can cause incorrect start index or false positives.

2. Step 2: Verify other lines

   Net array, prefix sums, and prefix difference checks are correct and standard.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing total gas check leads to incorrect results [OK]

Hint: Always check total gas >= total cost before searching start [OK]

Common Mistakes:

• Forgetting total gas check
• Misusing modulo in prefix sums
• Resetting start without resetting tank

5. What is the time complexity of the optimal greedy solution for Two City Scheduling that sorts by cost difference and assigns people in a single pass?

medium

A. O(n^2) because of nested loops to assign people

B. O(n log n) due to sorting the list of 2n people

C. O(n) since assignment is done in one pass after sorting

D. O(n log n) including sorting and constant time assignment

Solution

1. Step 1: Identify sorting cost

   Sorting 2n people by cost difference takes O(n log n) time.

2. Step 2: Identify assignment cost

   Assigning people in a single pass is O(n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting dominates, total complexity is O(n log n) [OK]

Hint: Sorting dominates time complexity [OK]

Common Mistakes:

• Assuming assignment is nested loop causing O(n^2)
• Ignoring sorting cost and claiming O(n)
• Confusing space complexity with time complexity