Remove K Digits (Monotonic Stack)

▶

Steps

setup

Initialize empty builder stack

Start with an empty list to simulate the stack that will hold digits of the resulting number.

💡 This empty stack will be used to build the minimal number by pushing and popping digits.

Line:

builder = []

💡 The stack starts empty, ready to process digits one by one.

fill_cells

Process first digit '1'

Read the first digit '1' and push it onto the empty stack.

💡 With an empty stack, the first digit is always pushed to start building the number.

Line:

for digit in num:
    builder.append(digit)

💡 The stack now contains '1', starting the minimal number.

fill_cells

Process second digit '4' - push without popping

Read digit '4'. Since '4' is greater than top of stack '1', push it without popping.

💡 We only pop if the current digit is smaller than the top and k > 0; here '4' is larger, so we push.

Line:

while k > 0 and builder and builder[-1] > digit:
    builder.pop()
    k -= 1
builder.append(digit)

💡 Stack maintains monotonic increasing order by pushing larger digits on top.

fill_cells

Process third digit '3' - pop '4' then push '3'

Digit '3' is smaller than top '4' and k=3>0, so pop '4' and decrement k. Then push '3'.

💡 Popping larger digits before smaller ones reduces the number; this is the greedy removal step.

Line:

while k > 0 and builder and builder[-1] > digit:
    builder.pop()
    k -= 1
builder.append(digit)

💡 Removing '4' makes the number smaller; k decreases from 3 to 2.

fill_cells

Process fourth digit '2' - pop '3' then push '2'

Digit '2' < top '3' and k=2>0, pop '3' and decrement k. Then push '2'.

💡 Continuing greedy removal to keep number minimal by removing larger digits before smaller ones.

Line:

while k > 0 and builder and builder[-1] > digit:
    builder.pop()
    k -= 1
builder.append(digit)

💡 Removing '3' reduces k to 1 and keeps stack monotonic increasing.

fill_cells

Process fifth digit '2' - push without popping

Digit '2' equals top '2', so push it without popping.

💡 No removal needed since current digit is not smaller than top of stack.

Line:

while k > 0 and builder and builder[-1] > digit:
    builder.pop()
    k -= 1
builder.append(digit)

💡 Stack can have equal digits; monotonic non-decreasing order is maintained.

fill_cells

Process sixth digit '1' - pop '2', then push '1'

Digit '1' < top '2' and k=1>0, pop one '2' and decrement k to 0. Since k=0, stop popping. Push '1'.

💡 Removals stop when k reaches zero, even if current digit is smaller than top.

Line:

while k > 0 and builder and builder[-1] > digit:
    builder.pop()
    k -= 1
builder.append(digit)

💡 Only one removal left, so only one '2' popped; stack after popping is ['1', '2'], then push '1'.

fill_cells

Process seventh digit '9' - push without popping

Digit '9' > top '1', push it without popping since k=0.

💡 No removals left, so all remaining digits are pushed.

Line:

while k > 0 and builder and builder[-1] > digit:
    builder.pop()
    k -= 1
builder.append(digit)

💡 Stack now contains all remaining digits after removals.

shrink

No removals left (k=0), skip trimming

Since k=0, no digits are removed from the end of the stack.

💡 If k was still positive, we would remove digits from the end to minimize the number.

Line:

if k > 0:
    builder = builder[:-k]

💡 All removals done during iteration; no trailing removals needed.

prune

Remove leading zeros (none here)

Strip leading zeros from the stack content; none exist here.

💡 Leading zeros do not affect numeric value and must be removed for correct output.

Line:

result = ''.join(builder).lstrip('0')

💡 No leading zeros means the number is already minimal in format.

reconstruct

Return final answer

Return the final minimal number '1219' or '0' if empty.

💡 If all digits were removed, return '0' to represent zero.

Line:

return result if result else '0'

💡 The algorithm produces the smallest number after removing k digits.

def removeKdigits(num: str, k: int) -> str:
    builder = []  # STEP 1: initialize empty stack
    for i, digit in enumerate(num):  # STEP 2-8: process each digit
        while k > 0 and builder and builder[-1] > digit:  # STEP 3: pop if top > current digit
            builder.pop()  # STEP 4-7: pop operation
            k -= 1
        builder.append(digit)  # STEP 2-8: push current digit
    if k > 0:  # STEP 9: remove trailing digits if k remains
        builder = builder[:-k]
    result = ''.join(builder).lstrip('0')  # STEP 10: remove leading zeros
    return result if result else '0'  # STEP 11: return final answer

if __name__ == '__main__':
    print(removeKdigits("1432219", 3))  # Expected: "1219"

📊

Remove K Digits (Monotonic Stack) - Watch the Algorithm Execute, Step by Step

Watching each push and pop operation reveals how the algorithm ensures the smallest possible number by removing larger digits before smaller ones.

no_op

Stack (top→bottom)

empty

pushElement[0]: 1

Stack (top→bottom)

1

↑ pushed: 1

pushElement[1]: 4

Stack (top→bottom)

4

1

↑ pushed: 4

popElement[2]: 3

Stack (top→bottom)

3

1

↓ popped: [4]

popElement[3]: 2

Stack (top→bottom)

2

1

↓ popped: [3]

pushElement[4]: 2

Stack (top→bottom)

2

2

1

↑ pushed: 2

popElement[5]: 1

Stack (top→bottom)

1

2

1

↓ popped: [2]

pushElement[6]: 9

Stack (top→bottom)

9

1

2

1

↑ pushed: 9

no_op

Stack (top→bottom)

9

1

2

1

no_op

Stack (top→bottom)

9

1

2

1

Contributes: "1219"

no_op

Stack (top→bottom)

9

1

2

1

Contributes: "1219"

Key Takeaways

✓ The greedy removal of digits larger than the current digit ensures the smallest possible number.

This is hard to see from code alone because the popping condition is inside a loop and depends on k and stack state.

✓ The stack maintains a monotonic non-decreasing sequence of digits, which is crucial for correctness.

Visualizing the stack shows how the algorithm preserves order and when it decides to pop or push.

✓ When k reaches zero, no more removals happen, and remaining digits are simply appended.

This explains why some digits remain even if they are larger than the current digit, which might be confusing without tracing.

Practice

1. Given the following code for largestRectangleArea, what is the returned max_area for input heights = [2,1,2]?

easy

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Trace stack operations for heights=[2,1,2]

   i=0,h=2: stack=[0]; i=1,h=1: pop 0 (height=2,width=1), max_area=2; stack=[]; append 1; i=2,h=2: append 2; i=3,h=0: pop 2 (height=2,width=1), max_area=2; pop 1 (height=1,width=3), max_area=3

2. Step 2: Final max_area after processing all elements

   max_area=3

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Max rectangle area is 3 for input [2,1,2] [OK]

Hint: Remember to add sentinel zero to flush stack [OK]

Common Mistakes:

• Forgetting sentinel zero causes missed areas
• Incorrect width calculation
• Off-by-one in stack indices

2. What is the time complexity of the optimized stack-based approach for validating parentheses in a string of length n, and why might some candidates mistakenly think it is higher?

medium

A. O(n^2) because each character might be compared multiple times during matching

B. O(n) because each character is processed once with constant-time stack operations

C. O(n log n) due to sorting or ordering operations on the stack

D. O(n) for time but O(n^2) for space due to stack growth in worst case

Solution

1. Step 1: Identify complexity of outer loop

   The algorithm iterates over each character exactly once, so the loop is O(n).

2. Step 2: Check stack operations

   Stack push/pop are O(1) operations, so total time remains O(n). No nested loops or repeated scanning.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Single pass with constant-time stack ops -> O(n) time [OK]

Hint: Each character processed once with O(1) stack ops [OK]

Common Mistakes:

• Confusing with brute force O(n^2) approach

3. Suppose the calculator must now support expressions where numbers can be reused multiple times (e.g., "2*2*2") and the input length can be very large. Which modification to the optimal approach is necessary to handle this efficiently?

hard

A. Switch to a brute force left-to-right evaluation ignoring precedence to reduce complexity.

B. Implement memoization to cache results of subexpressions to avoid recomputation.

C. Use a stack to immediately evaluate multiplication and division, but keep track of last_num to handle repeated operations efficiently.

D. Use recursion with backtracking to explore all possible reuse combinations.

Solution

1. Step 1: Understand reuse impact

   Repeated multiplication/division requires immediate evaluation to maintain precedence and efficiency.

2. Step 2: Identify suitable approach

   Using a stack or stack-like variables to immediately compute * and / handles repeated operations efficiently without extra overhead.

3. Step 3: Reject alternatives

   Brute force ignores precedence, memoization is unnecessary for linear evaluation, recursion/backtracking is inefficient.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Immediate evaluation with stack variables handles reuse and large inputs efficiently [OK]

Hint: Immediate evaluation with stack variables handles repeated ops efficiently [OK]

Common Mistakes:

• Ignoring precedence in reuse
• Using recursion unnecessarily
• Trying brute force for efficiency

4. Suppose the problem is modified so that the input string can contain not only '(' and ')' but also '*' characters, where '*' can represent either '(' or ')' or an empty string. Which approach is best suited to handle this variant efficiently?

hard

A. Use dynamic programming to track valid substring lengths considering '*' as wildcards.

B. Use the two-pass counter approach ignoring '*' characters.

C. Use brute force checking all substrings and validating with '*' replacements.

D. Use a stack-based approach tracking indices and possible '*' substitutions.

Solution

1. Step 1: Understand the complexity introduced by '*'

   The '*' character can represent multiple possibilities, requiring tracking multiple states.

2. Step 2: Evaluate approaches for handling wildcards

   Dynamic programming can efficiently track valid substring lengths considering '*' as '(', ')' or empty, unlike counters or naive stack approaches.

3. Step 3: Rule out brute force due to exponential possibilities

   Brute force checking all substrings with '*' replacements is infeasible for large inputs.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP handles wildcard substitutions efficiently [OK]

Hint: DP handles wildcard '*' efficiently [OK]

Common Mistakes:

• Ignoring '*' in counters
• Assuming stack alone can handle wildcards
• Trying brute force for large inputs

5. Suppose the problem is modified so that the input string may contain wildcard characters '*' that can represent either an opening bracket, a closing bracket, or an empty string. Which of the following approaches correctly adapts the stack-based solution to handle this variant efficiently?

hard

A. Use a brute force approach to try all replacements of '*' and check validity

B. Replace all '*' with empty strings and run the original stack-based validation

C. Use two stacks to track possible opening and closing brackets positions and validate ranges

D. Ignore '*' characters and validate only the remaining brackets with the original stack approach

Solution

1. Step 1: Understand wildcard impact

   Wildcards can represent multiple bracket types or empty, so a single stack is insufficient to track all possibilities.

2. Step 2: Use two stacks approach

   One stack tracks positions of opening brackets, another tracks positions of '*'. This allows matching '*' as needed to balance brackets efficiently in one pass.

3. Step 3: Reject invalid sequences

   After processing, ensure all unmatched opening brackets can be matched by '*' positions appearing after them.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Two stacks track brackets and wildcards to handle all cases [OK]

Hint: Two stacks track brackets and wildcards for flexible matching [OK]

Common Mistakes:

• Replacing '*' blindly or ignoring them causes incorrect results