402. Remove K Digits
Model: qwen3.5:9b
Topics: Stack,Greedy
FAANG asked: 1
Acceptance rate: 28.7%
Problem Breakdown
We are given a non-negative integer as a string and an integer . We must remove exactly digits from this number such that the remaining sequence of digits forms the smallest possible numerical value.
Inputs:
num: String representing a non-negative integer (no leading zeros initially).k: Integer, count of digits to remove ( usually, though constraints say length ).
Outputs:
- A string representing the smallest possible number after removal.
Constraints & Edge Cases:
- Leading Zeros in Output: The resulting number must not have leading zeros (e.g., “05” becomes “5”). If all digits are removed or only zeros remain, return “0”.
- Monotonicity: Since we want the smallest value, smaller digits should appear as early (left) as possible in the result sequence.
- Subsequence Order: We cannot reorder digits; we can only delete them to form a subsequence of length .
Intuition
A brute-force approach would try all combinations of removing indices, which is combinatorially expensive (). This won’t scale for large strings.
To minimize the number value lexicographically:
- We want smaller digits at more significant positions (the left side).
- If we encounter a digit that is smaller than the previous digit, and we still have removals available (), it makes sense to remove the larger previous digit. This allows the current smaller digit to shift into a higher significance position sooner.
This suggests maintaining an increasing sequence of digits in our result buffer (a stack). If the next incoming digit is smaller than what’s at the top of this “result so far,” we pop the larger one and decrement . We repeat until the condition isn’t met or we run out of removals.
Approach
- Initialize an empty list
stackto act as our monotonic increasing stack (representing digits kept). - Iterate through each digit in
num. - While the stack is not empty, and the current digit is smaller than the top element of the stack (
stack[-1] > num[i]), AND we still have removals left ():- Pop from the stack (remove that larger digit).
- Decrement .
- Push the current digit onto the stack.
- After iterating through all digits, if , it means we still need to remove more digits because the sequence was non-decreasing at the end. Pop from the end of the stack until reaches 0 (removing largest trailing digits).
- Join the remaining elements in
stackinto a string. - Strip leading zeros using
.lstrip('0'). If empty, return “0”.
Complexity Analysis
- Time: where is length of
num. Each digit is pushed onto the stack once and popped at most once (either during the while loop or after iteration). - Space: to store the digits in the stack. The output string also takes .
Solution
def removeKdigits(num: str, k: int) -> str:
# Stack to build the smallest number lexicographically
stack = []
for digit in num:
# While we can still remove digits (k > 0),
# and current digit is smaller than top of stack.
while k > 0 and stack and stack[-1] > digit:
stack.pop()
k -= 1
stack.append(digit)
# If k > 0, remove remaining digits from the end (largest trailing ones)
if k > 0:
stack = stack[:-k]
result = "".join(stack).lstrip('0')
return "0" if not result else result
Edge Cases Handled
- All digits removed: If
len(num) == k, the loop finishes, then we strip everything. The check at the end returns"0"correctly for empty results or all-zeros strings (e.g., input “10”, k=2 -> stack becomes [‘1’,‘0’], pop ‘1’, becomes 1, push ‘0’. After loop, slice removes remaining digit). Result is empty string which converts to “0”. - Leading zeros in output: Handled by
.lstrip('0'). If result becomes empty string (e.g., input “10”, k=2), it returns"0". - Increasing sequence (e.g.
num="12345", k=2): The while loop never triggers inside the iteration because digits are increasing. After loop, remains 2. We slice off last 2 elements (stack[:-2]). - Decreasing sequence: Handled by popping during iteration immediately when a smaller digit is found.