Remove K Digits
Asked at Microsoft
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Microsoft | MEDIUM | View all Microsoft questions → |
How to Think About It
Brute force: try all combinations of removing k digits and pick the minimum (exponential).
Use a monotonic increasing stack to greedily remove larger digits first.
For each digit, while the stack top is larger and we still have removals left, pop from the stack.
After processing all digits, if removals remain, trim from the end (stack is non-decreasing).
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.
What Trips People Up in Real Interviews
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.
Solution Code
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'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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.