Remove K Digits

Medium
monotonic-stack

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

Key Insight: To minimize the number, we want smaller digits at the front. Use a monotonic increasing stack: whenever we see a digit smaller than the stack top, pop larger digits (if we still have removals left).

Greedy Strategy:

  1. Iterate through digits left to right
  2. While stack is non-empty, stack top > current digit, and k > 0: pop the stack (remove that digit)
  3. Push the current digit
  4. If k > 0 after processing all digits, remove from the end
  5. Strip leading zeros and handle edge case of empty result

Why this works: A larger digit followed by a smaller digit creates an opportunity - removing the larger digit shifts smaller digits left, reducing the overall number.

Example 1

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove 4, 3, and 2 to get 1219, which is the smallest possible.

Example 2

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1, leaving "0200" which becomes "200".

Example 3

Input: num = "10", k = 2
Output: "0"
Explanation: Remove both digits. The result is "0".

Constraints

  • 1 <= k <= num.length <= 10^5
  • num consists of only digits
  • num does not have any leading zeros except for the zero itself
Show Hints (4)
Hint 1: To minimize a number, we want smaller digits as far left as possible.
Hint 2: If we see a digit smaller than the previous one, removing the previous makes the number smaller.
Hint 3: Use a monotonic increasing stack - pop larger digits when a smaller one appears.
Hint 4: After processing, if k > 0, remove from the right. Finally, strip leading zeros.
Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor
Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?