Bird
Raised Fist0

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)?

easy🧾 Code Trace Q12 of Q15
Greedy Algorithms - Remove K Digits (Smallest Number)
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'
A"14"
B"13"
C"12"
D"32"
Step-by-Step 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]
Quick Trick: Pop larger digits when smaller digit found until k=0 [OK]
Common Mistakes:
MISTAKES
  • Not popping enough digits when smaller digit appears
  • Removing digits from front only
  • Forgetting to strip leading zeros
Trap Explanation:
PITFALL
  • Candidates often forget to pop multiple times or stop early, leading to wrong output.
Interviewer Note:
CONTEXT
  • Tests ability to mentally execute greedy stack code and track variables.
Master "Remove K Digits (Smallest Number)" 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