Remove K Digits

Remove K Digits

What is this problem about?

The Remove K Digits interview question gives you a non-negative integer represented as a string and an integer k. You must remove exactly k digits from the number string to produce the smallest possible resulting number. The result should not have leading zeros (unless the result is "0" itself). This is a classic greedy problem with an elegant monotonic stack solution.

Why is this asked in interviews?

This problem is asked at Apple, Cisco, Samsung, Microsoft, Meta, Amazon, Google, Bloomberg, and Adobe because it exemplifies the greedy "locally optimal" strategy: always remove a digit that is followed by a smaller digit, as this reduces the number's value most. The monotonic stack makes this greedy intuition efficient. It also introduces digit-string arithmetic, which appears in financial and data processing systems.

Algorithmic pattern used

The pattern is a monotonic (non-decreasing) stack. Iterate through each digit. While the stack is non-empty, the top of the stack is greater than the current digit, and we still have removals left (k > 0), pop the top digit (this is our greedy removal). Push the current digit. After processing all digits, if k > 0 still, pop from the end (the largest trailing digits). Finally, strip any leading zeros from the result.

Example explanation

Number: "1432219", k = 3.

• Push 1. Stack: [1]
• Push 4. Stack: [1,4]
• 3 < 4: pop 4 (k=2). 3 > 1: push. Stack: [1,3]
• 2 < 3: pop 3 (k=1). 2 > 1: push. Stack: [1,2]
• 2 == 2: push. Stack: [1,2,2]
• 1 < 2: pop 2 (k=0). 1 < 2: but k=0, stop. Push 1. Stack: [1,2,1]
• 9: push. Stack: [1,2,1,9]

Result: "1219".

Common mistakes candidates make

• Forgetting to handle k > 0 after the loop — any remaining removals should pop from the stack's right end.
• Not stripping leading zeros from the final result (e.g., result "0200" → "200").
• Returning an empty string instead of "0" when all digits are removed.
• Using a simple sort instead of the greedy stack, which changes the digit order.

Interview preparation tip

For the Remove K Digits coding problem, the monotonic stack and greedy interview pattern is your foundation. Practice building the stack mentally for two or three examples before coding. Interviewers at Snowflake and TikTok often test edge cases: k = length of number, or all digits are the same. Handling leading zeros cleanly with lstrip('0') or '0' in Python is a common trick worth memorizing.