Skip to main content

402. Remove K Digits

medium

Delete k digits from a number string to get the smallest possible result. A monotonic-stack greedy problem where the invariant clicks the moment you see it.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

Constraints

  • 1 <= k <= num.length <= 10^5
  • num consists of only digits.
  • num does not have any leading zeros except for the zero itself.

Examples

Example 1

Input
num = "1432219", k = 3
Output
"1219"

Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2

Input
num = "10200", k = 1
Output
"200"

Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3

Input
num = "10", k = 2
Output
"0"

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

To minimize the result, remove a digit that's bigger than the digit right after it — that 'descent' is wasted value.

Hint 2

That's a monotonic increasing stack: while you have remaining removals and the top exceeds the next digit, pop.

Hint 3

If you still have removals left at the end, trim from the right (the smallest result is in front).

Hint 4

Strip leading zeros at the end. If everything got removed, return '0'.

Solution approach

Reveal approach

Monotonic increasing stack. Walk num left to right. For each digit c, while the stack is non-empty AND stack.top() > c AND k > 0, pop the stack and decrement k. Then push c. After the scan, if k > 0 (we still need to remove some), pop k more times from the right of the stack. Build the string from the stack, strip leading zeros, and return it. If the result is empty, return '0'. The greedy is correct because every popped digit is strictly larger than its successor — removing it strictly decreases the prefix value at that position. O(n) time, O(n) space.

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • stack
  • monotonic-stack
  • greedy

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Remove K Digits and Stacks problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →