#402
Remove K Digits
Medium Monotonic increasing stack
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Remove k digits from a number string to make the smallest possible number. Return it without leading zeros ("0" if empty).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: remove k digits to make the smallest number.
Why this works: a digit followed by a smaller digit should go. Keep the kept digits increasing with a stack.
Example: "1432219", k = 3
4 removed by 3, 3 removed by 2, 2 removed by 1"1219"
✦Hints open one at a time
A digit followed by a smaller digit should be removed — that makes an earlier position smaller.
Keep the kept digits increasing using a stack.
If removals are left at the end, remove from the tail.
↗Approach
For each digit, while k > 0 and the last kept digit is bigger, pop it and decrement k. Append the digit. Trim k more from the end, strip leading zeros, return "0" if nothing is left.
</>Solution (Java)
class Solution {
public String removeKdigits(String num, int k) {
StringBuilder st = new StringBuilder(); // used as a stack
for (char c : num.toCharArray()) {
while (k > 0 && st.length() > 0 && st.charAt(st.length() - 1) > c) {
st.deleteCharAt(st.length() - 1); // bigger digit before a smaller one: remove it
k--;
}
st.append(c);
}
st.setLength(st.length() - k); // leftover removals from the end
int i = 0;
while (i < st.length() && st.charAt(i) == '0') i++;
String res = st.substring(i);
return res.isEmpty() ? "0" : res;
}
}!Common mistake
Forgetting leading zeros or the "0" for an empty result.
Complexity
- Time: O(n).
- Space: O(n).
Topic: Stack & Queue
🎬 Episodes 46–52: video coming soon