MediumStringStackGreedyMonotonic StackUpdated Sep 2026

402. Remove K Digits

Asked at Microsoft

Difficulty

Medium

Time

O(n)

Space

O(n)

Pattern

String

Companies

1

Problem

You are given a string num that holds a non-negative integer, and an integer k. Delete exactly k digits from num so that the digits that remain, read in their original order, form the smallest possible number.

You must keep the remaining digits in the same relative order — you can only remove digits, not rearrange them. Return the answer as a string, not as an integer.

The result must not have leading zeros. If every digit is removed, the answer is "0".

Delete k digits, keep the order

14322190123456The three red digits (4, 3, 2) are the ones we deleteresult = 121912190123The digits that survive keep their original order and form1219
We must drop exactly 3 digits from "1432219" and keep the rest in order; "1219" is the smallest result.

Constraints

  • ●1 <= k <= num.length <= 10^5
  • ●num contains only digit characters
  • ●num has no leading zeros, except when num itself is "0"

Examples

Example 1
Inputnum = "1432219", k = 3
Output"1219"
WhyRemoving 4, 3 and 2 leaves 1, 2, 1, 9 in order, which reads 1219. Any other choice of 3 digits to delete gives a bigger number.
Example 2
Inputnum = "10200", k = 1
Output"200"
WhyDeleting the leading 1 leaves "0200". We drop the leading zero, so the answer is "200".
Example 3
Inputnum = "10", k = 2
Output"0"
WhyBoth digits are removed, nothing is left, and by the rules the answer is "0".

Asked At

1 companies
CompanyDifficulty
MicrosoftMediumView all Microsoft questions →

How to Think About It

1

Brute force: try all combinations of removing k digits and pick the minimum (exponential).

2

Use a monotonic increasing stack to greedily remove larger digits first.

3

For each digit, while the stack top is larger and we still have removals left, pop from the stack.

4

After processing all digits, if removals remain, trim from the end (stack is non-decreasing).

5

Strip leading zeros and return the result or "0" if empty.

Optimal Approach

Use a monotonic increasing stack. Iterate through each digit: while the stack is not empty, the top is greater than the current digit, and we still have removals left, pop the top. Push the current digit. After the loop, if k is still positive, remove from the end. Convert the stack to a string, strip leading zeros, and return "0" if the result is empty. This is O(n) time and space.

Monotonic stack removes big digits first

stack1← topPush 1 — nothing to compare yetstack121← top4 and 3 were popped (k drops to 1), then 2, 2, 1 arepushed; the top 2 is bigger than the new 1, so it popstoostack1219← topPush 9; k is now 0, so no more removals happenwhile stack and k > 0 and stack[-1] > d: stack.pop(); k -= 1if k > 0: drop from the endstrip leading zeros, empty → "0"
A bigger digit sitting before a smaller one should go, so we pop it while we still have removals left.
ComplexityTime O(n)Space O(n)Each digit is pushed once and popped at most once, so the work is linear in the length of num; the stack can hold up to n digits.

What Trips People Up in Real Interviews

1

Clarify that the result should have no leading zeros.

2

Explain why greedy removal of larger preceding digits works.

3

Discuss why a monotonic stack is the right data structure.

4

Handle edge cases: k equals length of number, all zeros.

5

Mention that time complexity is O(n) since each element is pushed/popped once.

Solution Code

O(n) time
def removeKdigits(num, k):
    stack = []
    for d in num:
        while stack and k > 0 and stack[-1] > d:
            stack.pop()
            k -= 1
        stack.append(d)
    while k > 0:
        stack.pop()
        k -= 1
    result = ''.join(stack).lstrip('0')
    return result if result else '0'

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Remove K Digits problem?

Given a string num representing a non-negative integer and an integer k, remove k digits from the number so that the remaining digits form the smallest possible integer. Return the result as a string.

How do you solve Remove K Digits?

The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Remove K Digits?

Remove K Digits is asked at Microsoft. It is a medium difficulty problem.

What are common mistakes on Remove K Digits?
  • Clarify that the result should have no leading zeros.
  • Explain why greedy removal of larger preceding digits works.
  • Discuss why a monotonic stack is the right data structure.
  • Handle edge cases: k equals length of number, all zeros.
  • Mention that time complexity is O(n) since each element is pushed/popped once.