402. Remove K Digits

402

MediumStack and Expression ProcessingMonotonic stackMonotonic increasing stack (greedy digit removal)

Remove K Digits

Given a non-negative integer represented as a string num and an integer k, remove exactly k digits so that the resulting number is the smallest possible. Return the result as a string with no leading zeros, or "0" if the result is empty.

Open official problem prompt ↗

In plain English

Delete exactly k digits, keeping relative order, so the remaining digits form the smallest possible number.

Picture it like this

Like editing a mountain-range skyline down to a valley: whenever a tall peak is immediately followed by a lower point, you knock the peak down first because lower-early is smaller.

Example

Input: num = "1432219", k = 3
Output: "1219"
Why: Removing the digits 4, 3, and the second 2 leaves 1219, the smallest number reachable by deleting three digits.

Constraints

1 <= k <= num.length <= 10^5num consists of only digitsnum does not have any leading zeros except for the value 0 itself

Pattern lesson

See the pattern, then code

Monotonic increasing stack (greedy digit removal)

↗

Stack and Expression Processing

Nested structures, matching delimiters, undo behavior, or unresolved operations.. A number is smaller when a high-value digit sits in a less significant position, so whenever the current digit is smaller than the digit on top of the stack, popping that top (spending one removal) shrinks the number.

New words, made simpleKnow these before the algorithm

Monotonic increasing stack: A stack whose kept elements are non-decreasing from bottom to top after each step.
Leading zeros: Zeros at the front of the result that must be stripped, e.g. "0200" becomes "200".

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Try all deletions

Exponential — impossible for n up to 10^5.

Enumerate every choice of k digits to remove and take the minimum.

Time O(C(n,k))Space O(n)

Best choiceGreedy monotonic stack

Each digit is pushed and popped at most once, giving a single linear pass — the optimal solution.

Pop any kept digit larger than the incoming digit while removals remain, then trim leftover removals from the end.

Time O(n)Space O(n)

The rule we keep true

Invariant

The stack always holds the smallest-so-far subsequence achievable with the removals spent, kept in non-decreasing order except for digits that could not yet be improved.

Why this is correct

Reasoning

Placing a smaller digit in a more significant position always lowers the value, so popping a larger top whenever a smaller digit arrives is never regretted. If removals remain unused at the end, the sequence is already non-decreasing, so the largest remaining digits are at the tail and are cheapest to drop there.

The algorithm in three movesSay these aloud before coding

1Scan digits left to right, keeping a stack of kept digits

after '3': popped 4, stack=[1,3] k=2

2While removals remain and the top exceeds the current digit, pop the top and spend a removal

after second '1': popped 2 then 1-check, stack=[1,2,1] k=0

3Push the current digit

final stack=[1,2,1,9] -> "1219"

4If removals remain after the scan, trim them from the end

5Strip leading zeros and return "0" if empty

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Read'1'

2 · AskPop top>1?

3 · Update statestack=[1] k=3

4 · ResultPush 1

Key takeaway

Digits 4, 3, and a 2 are popped because a smaller digit follows each of them.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 4-7Greedy pop loop
Removes larger kept digits while a smaller digit arrives and removals remain, keeping the prefix as small as possible.
2
Lines 8Push current digit
Every scanned digit is a candidate to keep and joins the stack.
3
Lines 9Trim leftover removals
If k>0 the sequence is already increasing, so drop the k largest digits from the tail.
4
Lines 10-11Normalize output
Strip leading zeros and return "0" when everything was removed or was zero.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Removing every digit, e.g. num="10", k=2 gives "0"
Leading zeros exposed after removal, e.g. num="10200", k=1 gives "200"
Already increasing digits, e.g. num="12345", k=2 gives "123" (trim from end)
num length equal to k

Common beginner mistakes

Forgetting to trim leftover k when the input is monotonically non-decreasing
Returning an empty string instead of "0"
Not stripping leading zeros produced by removals
Using >= instead of > and needlessly removing equal digits, which can waste removals

Check your understanding

If after the main scan k removals still remain, why are they taken from the end of the stack?

Remove K Digits

Remove K Digits

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Stack and Expression Processing