Remove K Digits

Given a non-negative integer as a string num and an integer k, remove exactly k digits so the remaining number is the smallest possible. Return it as a string (with no leading zeros; return "0" if everything is removed or the result is empty).

Hints

· Stuck? Reveal one nudge at a time.

To make the number smallest, keep the most significant digits as small as possible.

When a smaller digit arrives, removing a larger digit to its left shrinks the number.

Use an increasing stack: pop larger digits (spending removals) before pushing.

Common doubts

A larger digit in a more significant position makes the number bigger. Replacing it with a smaller digit that comes right after reduces the value — the greedy local improvement.

The stack is non-decreasing, so the largest remaining digits sit at the end — drop the last k of them.

Popping can leave zeros at the front; strip them. If the string becomes empty, the answer is '0'.

Interview follow-ups

· What an interviewer asks next.

Flip the comparison: use a decreasing stack, popping smaller digits when a larger one arrives.

Track which indices are popped; the popped set (plus any trailing trim) are the removed digits.

Fun facts

This greedy is the string version of 'smallest subsequence' problems solved with a monotonic stack.
The same technique underlies 'Create Maximum Number' and 'Remove Duplicate Letters'.

Asked at

AmazonGoogleMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: num = "1432219", k = 3
Output: 1219
Removing 4, 3, and 2 leaves the smallest number 1219.

Example 2

Input: num = "10200", k = 1
Output: 200
Remove the leading 1 to get 0200, then strip the leading zero -> 200.

Constraints

- 1 <= k <= num.length <= 10^5 - num consists of only digits - num has no leading zeros except '0' itself

To make a number smallest, you want its leftmost (most significant) digits as small as possible. So whenever a digit is followed by a smaller one, deleting the larger left digit shrinks the number — and you should do that greedily while you still have removals to spend. That "remove a larger digit when a smaller one arrives" rule is a monotonic increasing stack.

Prerequisites

Before you start

· Concepts used directly in the solution.

Monotonic stack. A stack kept non-decreasing by popping larger digits when a smaller one arrives.

Positional value. Earlier (more significant) digits dominate the number's size.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The rules

“Remove exactly k, or at most k?”

Exactly k — if you don't need them all mid-string, drop the rest from the end.

“How are leading zeros and an empty result handled?”

Strip leading zeros; if nothing remains, return "0".

The ideal opening — say it like this

Smallest number means keeping the earliest digits as small as possible.

So I scan left to right with an increasing stack, popping a larger digit whenever a smaller one comes and I still have removals.

Any leftover removals I take from the end, then strip leading zeros.

Understand the problem

Worked example — num = "1432219", k = 3

1 -> [1]
4 -> [1,4]
3 -> pop 4 (k=2) -> [1,3]
2 -> pop 3 (k=1) -> [1,2]
2 -> [1,2,2]
1 -> pop 2 (k=0) -> [1,2,1]
9 -> [1,2,1,9]
result "1219"

Key observations

1Aha

Remove a larger digit as soon as a smaller one appears

A larger digit in a more significant place inflates the number. When a smaller digit follows, popping the larger one (if you have budget) yields a smaller result.

2Aha

Leftover removals come off the end

If removals remain after the scan, the stack is non-decreasing, so its largest digits are the trailing ones — remove those.

3Aha

Clean up leading zeros

Popping can expose leading zeros; strip them, and return "0" if the string empties out.

Brute force vs optimal

	Remove one at a time	Monotonic stack
Idea	k passes, each deletes the first digit bigger than its successor	One pass, pop larger digits greedily
Time	O(n * k)	O(n)
Space	O(n)	O(n)

Full code is in the Approaches selector below.

Summary

Key takeaway

Scan left to right with an increasing stack: while you have removals and the top digit exceeds the incoming one, pop it; then push. Drop any leftover removals from the end, strip leading zeros, and return "0" if empty. O(n).

stack = []
for d in num:
    while k and stack and stack.top > d: pop; k -= 1
    push d
if k: stack = stack[:-k]
return join(stack) stripped of leading zeros, or "0"