LeetCode 402 - Remove K Digits
The problem gives us a numeric string num and an integer k. We must remove exactly k digits from the number so that the resulting integer is as small as possible. The key detail is that we are not allowed to reorder digits.
Difficulty: 🟡 Medium
Topics: String, Stack, Greedy, Monotonic Stack
Solution
Problem Understanding
The problem gives us a numeric string num and an integer k. We must remove exactly k digits from the number so that the resulting integer is as small as possible.
The key detail is that we are not allowed to reorder digits. We may only delete digits while preserving the relative order of the remaining characters. After removing digits, the result should not contain leading zeros. If every digit is removed, or if the remaining digits become all zeros after trimming leading zeros, the answer should be "0".
For example, if num = "1432219" and k = 3, we want the smallest number obtainable by deleting three digits. Removing 4, 3, and one 2 gives "1219", which is the smallest possible result.
The input size is important. The constraint num.length <= 10^5 means the algorithm must be close to linear time. Any solution that tries every possible combination of deletions would be far too slow. This strongly suggests we need a greedy strategy combined with an efficient data structure.
Several edge cases are important:
- Removing all digits, such as
num = "10", k = 2, should return"0". - Removing digits may create leading zeros, such as
"10200"becoming"0200", which must be converted to"200". - Numbers that are already increasing, such as
"12345", require removing digits from the end. - Numbers that are decreasing, such as
"54321", benefit from removing earlier large digits. - Duplicate digits must be handled carefully because removing the wrong occurrence can lead to a larger final number.
Approaches
Brute Force Approach
A brute force solution would try every possible way to remove k digits from the string. For each candidate result, we would compare it numerically and keep the smallest one.
For a string of length n, we must choose k digits to remove, which creates C(n, k) possible combinations. This grows exponentially for large inputs. Even for moderate values of n, the number of possibilities becomes enormous.
This approach is correct because it checks every valid result, but it is completely impractical for n up to 100000.
Optimal Greedy + Monotonic Stack Approach
The important observation is that larger digits appearing before smaller digits should usually be removed first.
Suppose we have "143...". If we keep 4 before a smaller digit like 3, the resulting number becomes larger. Therefore, whenever we encounter a digit smaller than the previous digit, we should consider removing the previous larger digit.
This naturally leads to a monotonic increasing stack:
- We process digits from left to right.
- While the current digit is smaller than the top of the stack, and we still have removals available, we pop the larger digit from the stack.
- This greedily ensures that smaller digits appear earlier in the final number.
The stack remains monotonically increasing because larger digits are removed whenever a smaller digit arrives.
After processing all digits:
- If removals remain, we remove digits from the end because those are the largest remaining positions.
- Then we strip leading zeros.
- If nothing remains, return
"0".
This greedy strategy works because the leftmost digits contribute most heavily to the final numeric value. Making earlier digits as small as possible always improves the result.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | Exponential, roughly O(C(n, k) * n) | O(n) | Tries every possible deletion combination |
| Optimal | O(n) | O(n) | Uses a monotonic increasing stack with greedy deletions |
Algorithm Walkthrough
- Initialize an empty stack.
The stack will store digits of the final number as we build it. We want the stack to remain monotonically increasing whenever possible.
2. Iterate through each digit in num.
For every digit, compare it with the top of the stack. 3. While the stack is not empty, the top digit is larger than the current digit, and we still have removals available, pop from the stack.
This is the greedy step. A larger digit before a smaller digit increases the number unnecessarily. Removing the larger digit produces a smaller result. 4. Push the current digit onto the stack.
After removing any larger preceding digits, we add the current digit to the growing result.
5. After processing all digits, check whether k is still greater than zero.
If removals remain, the digits in the stack are already monotonically increasing. In this situation, removing digits from the end minimizes the number.
6. Remove the remaining k digits from the end of the stack.
These trailing digits are the least valuable to keep because earlier positions are more significant. 7. Convert the stack into a string.
Join all remaining digits together. 8. Remove leading zeros.
The problem requires that the final number contain no leading zeros.
9. If the resulting string is empty, return "0".
This handles cases where all digits were removed or all remaining digits became zeros.
Why it works
The algorithm maintains the invariant that the stack always represents the smallest possible prefix after processing each digit. Whenever a smaller digit appears, removing larger preceding digits improves the number at the earliest possible position, which has the greatest impact on the final value. Because each deletion is locally optimal and never harms future decisions, the greedy strategy produces the globally smallest result.
Python Solution
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
stack: list[str] = []
for digit in num:
while k > 0 and stack and stack[-1] > digit:
stack.pop()
k -= 1
stack.append(digit)
# Remove remaining digits from the end
while k > 0:
stack.pop()
k -= 1
# Build result and remove leading zeros
result = "".join(stack).lstrip("0")
return result if result else "0"
The implementation follows the greedy monotonic stack strategy directly.
The stack stores digits that will form the final answer. During iteration, the while loop removes larger digits whenever a smaller current digit appears. This ensures the left side of the number remains as small as possible.
After processing every digit, there may still be removals left. This occurs when the number is already increasing, such as "12345". In that situation, the largest contribution comes from the trailing digits, so we remove them from the end.
The final result is constructed with "".join(stack). The call to lstrip("0") removes leading zeros efficiently. If all digits disappear, we return "0".
Go Solution
func removeKdigits(num string, k int) string {
stack := make([]byte, 0)
for i := 0; i < len(num); i++ {
digit := num[i]
for k > 0 && len(stack) > 0 && stack[len(stack)-1] > digit {
stack = stack[:len(stack)-1]
k--
}
stack = append(stack, digit)
}
// Remove remaining digits from the end
for k > 0 {
stack = stack[:len(stack)-1]
k--
}
// Remove leading zeros
start := 0
for start < len(stack) && stack[start] == '0' {
start++
}
result := string(stack[start:])
if result == "" {
return "0"
}
return result
}
The Go implementation uses a []byte slice as the stack because digits are characters. Appending and slicing make push and pop operations efficient.
Unlike Python, Go does not provide a built in lstrip method, so leading zeros are removed manually using an index pointer.
Go strings are immutable, so converting the byte slice back into a string is necessary before returning the result.
Worked Examples
Example 1
Input:
num = "1432219"
k = 3
| Step | Current Digit | Stack Before | Action | Stack After | k |
|---|---|---|---|---|---|
| 1 | 1 | [] | Push 1 | [1] | 3 |
| 2 | 4 | [1] | Push 4 | [1,4] | 3 |
| 3 | 3 | [1,4] | Pop 4, push 3 | [1,3] | 2 |
| 4 | 2 | [1,3] | Pop 3, push 2 | [1,2] | 1 |
| 5 | 2 | [1,2] | Push 2 | [1,2,2] | 1 |
| 6 | 1 | [1,2,2] | Pop 2, push 1 | [1,2,1] | 0 |
| 7 | 9 | [1,2,1] | Push 9 | [1,2,1,9] | 0 |
Final result:
"1219"
Example 2
Input:
num = "10200"
k = 1
| Step | Current Digit | Stack Before | Action | Stack After | k |
|---|---|---|---|---|---|
| 1 | 1 | [] | Push 1 | [1] | 1 |
| 2 | 0 | [1] | Pop 1, push 0 | [0] | 0 |
| 3 | 2 | [0] | Push 2 | [0,2] | 0 |
| 4 | 0 | [0,2] | Push 0 | [0,2,0] | 0 |
| 5 | 0 | [0,2,0] | Push 0 | [0,2,0,0] | 0 |
Joined result:
"0200"
After removing leading zeros:
"200"
Example 3
Input:
num = "10"
k = 2
| Step | Current Digit | Stack Before | Action | Stack After | k |
|---|---|---|---|---|---|
| 1 | 1 | [] | Push 1 | [1] | 2 |
| 2 | 0 | [1] | Pop 1, push 0 | [0] | 1 |
After traversal, k = 1, so remove one more digit from the end.
Final stack:
[]
Result becomes:
"0"
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each digit is pushed and popped at most once |
| Space | O(n) | The stack may store all digits |
Although there is a nested while loop, the total number of pop operations across the entire algorithm is at most n. Each digit enters the stack once and leaves at most once. Therefore, the total runtime remains linear.
The auxiliary space complexity is also linear because the stack can contain up to all digits in the input.
Test Cases
solution = Solution()
assert solution.removeKdigits("1432219", 3) == "1219" # standard mixed digits
assert solution.removeKdigits("10200", 1) == "200" # leading zeros after removal
assert solution.removeKdigits("10", 2) == "0" # remove all digits
assert solution.removeKdigits("12345", 2) == "123" # increasing sequence
assert solution.removeKdigits("54321", 2) == "321" # decreasing sequence
assert solution.removeKdigits("11111", 3) == "11" # duplicate digits
assert solution.removeKdigits("10001", 1) == "1" # multiple leading zeros
assert solution.removeKdigits("9", 1) == "0" # single digit removal
assert solution.removeKdigits("112", 1) == "11" # remove trailing larger digit
assert solution.removeKdigits("1173", 2) == "11" # greedy middle removals
assert solution.removeKdigits("100200", 1) == "200" # internal zeros
assert solution.removeKdigits("765028321", 5) == "221" # complex greedy behavior
| Test | Why |
|---|---|
"1432219", 3 |
Standard example with multiple pops |
"10200", 1 |
Verifies leading zero trimming |
"10", 2 |
Verifies complete deletion |
"12345", 2 |
Increasing sequence, removes from end |
"54321", 2 |
Decreasing sequence, many greedy pops |
"11111", 3 |
Duplicate digits |
"10001", 1 |
Produces many leading zeros |
"9", 1 |
Smallest possible input |
"112", 1 |
Keeps equal digits correctly |
"1173", 2 |
Tests greedy removals in middle |
"100200", 1 |
Handles zeros inside number |
"765028321", 5 |
Stress test for repeated popping |
Edge Cases
One important edge case occurs when all digits are removed. For example, num = "10" and k = 2. A buggy implementation might return an empty string instead of "0". The solution handles this by checking whether the final processed string is empty and returning "0" in that case.
Another critical edge case involves leading zeros. Consider "10200" with k = 1. Removing the leading 1 creates "0200". If leading zeros are not removed, the output would violate the problem requirements. The implementation explicitly strips leading zeros before returning the result.
A third important edge case is when the digits are already in increasing order, such as "12345". In this scenario, the greedy popping condition never triggers during traversal. A naive implementation might forget to use any remaining removals. The algorithm correctly handles this by removing leftover digits from the end after iteration completes.
A fourth subtle edge case involves repeated equal digits, such as "11111". The algorithm only removes digits when the top of the stack is strictly greater than the current digit. This preserves stability among equal digits and avoids unnecessary deletions that could produce a larger final number later.