DSA problem
Remove K Digits
Given a string num representing a non-negative integer and an integer k, return the smallest possible integer (as a string) after removing exactly k digits from num. The remaining digits must preserve their original order. The output should not have leading zeros except for the value "0" itself.
To minimise the resulting number, we want the most-significant remaining digits to be as small as possible. This suggests a greedy decision: whenever we see a digit that is smaller than the previous digit we kept, the previous digit was "too big" and should be removed if we still have budget — removing it reduces a more-significant place than removing any later digit.
This greedy turns into a beautiful monotonic non-decreasing stack of digits. Iterate over num left-to-right; while the stack's top digit is strictly greater than the current digit and k > 0, pop and decrement k. Push the current digit. After the iteration, if k is still positive (the input is non-decreasing and we never popped enough), drop the last k digits from the stack. Finally, strip leading zeros and return; the empty result becomes "0".
The amortized cost is O(n) because each digit is pushed and popped at most once. This is one of the cleanest applications of monotonic stacks because the data structure directly mirrors the greedy invariant.
Examples
num = "1432219", k = 3"1219"num = "10200", k = 1"200"num = "10", k = 2"0"Constraints
- 1 <= k <= num.length <= 10^5
- num consists of only digits.
- num does not have any leading zeros except for the value "0" itself.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.