Bird
Raised Fist0

Identify the bug in the following code snippet for the Maximum Units on a Truck problem:

medium🐞 Bug Identification Q14 of Q15
Greedy Algorithms - Maximum Units on a Truck
Identify the bug in the following code snippet for the Maximum Units on a Truck problem:
def maximumUnits(boxTypes, truckSize):
    boxTypes.sort(key=lambda x: x[1])  # Sort ascending instead of descending
    totalUnits = 0
    for boxes, units in boxTypes:
        if truckSize == 0:
            break
        take = min(boxes, truckSize)
        totalUnits += take * units
        truckSize -= take
    return totalUnits
ALine 2: Sorting boxTypes in ascending order instead of descending
BLine 5: Missing check for truckSize == 0
CLine 7: Incorrect calculation of take using min(boxes, truckSize)
DLine 8: Incorrect update of totalUnits by multiplying take and units
Step-by-Step Solution
Solution:
  1. Step 1: Examine sorting order

    Sorting ascending by units per box causes picking boxes with lowest units first, leading to suboptimal total units.
  2. Step 2: Verify other lines

    Check for early stopping (line 5) is correct; min calculation and totalUnits update are correct.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Sorting order is critical for greedy correctness [OK]
Quick Trick: Sort descending by units per box to maximize units [OK]
Common Mistakes:
MISTAKES
  • Sorting ascending instead of descending
  • Forgetting to break when truckSize=0
  • Off-by-one in min calculation
Trap Explanation:
PITFALL
  • Sorting ascending looks plausible but breaks greedy optimality, causing wrong answers on many inputs.
Interviewer Note:
CONTEXT
  • Tests if candidate can spot subtle but critical sorting order bugs.
Master "Maximum Units on a Truck" in Greedy Algorithms

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Greedy Algorithms Quizzes