Remove K Digits
Understanding the Problem
We have a number represented as a string, and we need to remove exactly k digits from it to make the remaining number as small as possible. The digits stay in their original relative order (we delete digits, never reorder them).
The significance of a digit depends on its position. A larger digit sitting in a more significant position (further left) contributes more to the overall value. To minimize the number, we want smaller digits to appear as early as possible.
Consider "1432219" with one digit to remove. Scanning left to right, the first place where a digit is larger than the one right after it is the 4, which is followed by 3. Removing the 4 gives "132219", which is smaller than the result of removing any other single digit. This greedy observation is the foundation for the optimal solution.
Key Constraints:
1 <= k <= num.length <= 10^5- The string can be up to 100,000 characters long, so the solution needs to run in linear or near-linear time. Anything that enumerates combinations is far too slow.numconsists of only digits - No negative signs and no decimal points, so character comparison maps directly to digit comparison.k <= num.length- Whenkequals the length, every digit is removed and the answer is "0".
Approach 1: Brute Force (Try All Combinations)
Intuition
Try every possible way to remove k digits and pick the one that gives the smallest number. With n digits and k removals, this means choosing which n - k digits to keep, in their original order.
This is essentially generating all C(n, k) subsequences of length n - k, converting each to a number, and tracking the minimum.
Algorithm
- Generate all combinations of
n - kindices from the original string. - For each combination, build the subsequence string from those indices.
- Strip leading zeros and compare with the current minimum.
- Return the smallest result found.
Visualization and Code
Loading animation...
- Time Complexity: O(C(n, k) * n). We generate all C(n, k) combinations, and for each one we build a string of length n - k. For large n and moderate k, this is exponential.
- Space Complexity: O(n). The recursion depth is at most n - k, and we store one candidate string at a time.
Enumerating every combination is exponential and unusable for large inputs. The greedy observation from earlier removes the need for enumeration: a single left-to-right pass can decide each removal locally.
Approach 2: Greedy with Stack (Optimal)
Intuition
To make the result as small as possible, smaller digits should sit in the more significant (leftward) positions. So as we scan left to right, whenever a digit is smaller than the one immediately before it, removing that larger preceding digit lowers the number.
A stack carries this out cleanly. We push digits one by one. Before pushing a new digit, we compare it against the top of the stack. While the top is larger than the incoming digit and removals remain, we pop the top and count it as a removal. The stack therefore holds a non-decreasing sequence of digits read left to right, which is the smallest arrangement reachable from the prefix seen so far.
Two cases remain after the main loop. If removals are still left (k > 0), the stack is already non-decreasing, so removing from the end deletes the largest trailing digits. The result also needs its leading zeros stripped.
In a number with a fixed count of digits, an earlier position outweighs every position after it combined. So when digit d[i] is larger than d[i+1], removing d[i] produces a smaller result than removing any single digit at or after position i+1. Removing the leftmost such descent first is therefore safe: no other removal of one digit beats it.
The stack keeps the kept digits in non-decreasing order. A pop happens only when the new digit is smaller than the top, which is exactly the descent case above. If removals remain after the scan, the stack is already non-decreasing, so the largest digits sit at the end and removing from the end is the correct final step.
Algorithm
- Initialize an empty stack (or use a StringBuilder/list as a stack).
- For each digit in
num: - While the stack is not empty, the top of the stack is greater than the current digit, and k > 0: pop from the stack and decrement k.
- Push the current digit onto the stack.
- If k is still greater than 0, remove the last k digits from the stack (they are the largest remaining digits).
- Build the result from the stack, strip leading zeros.
- If the result is empty, return "0".
Visualization and Code
Loading animation...
- Time Complexity: O(n). Each digit is pushed onto the stack exactly once and popped at most once, giving at most 2n operations total.
- Space Complexity: O(n). The stack can hold up to n digits in the worst case (when the input is already in non-decreasing order).