Remove K Digits
MediumGreedily drop a digit bigger than its successor
Problem
Remove k digits from a number string to make the smallest possible resulting number.
Walk digits, popping any bigger digit on the stack while you still have removals left — keeps it smallest.
The idea
To make the smallest number, remove any digit that is larger than the one after it — the leftmost such removal shrinks the most significant position possible. A monotonic increasing stack performs exactly those removals in one pass.
The trick
- If removals remain after the pass, drop them from the end.
- Strip leading zeros afterwards, and return '0' if nothing is left.
- O(n) with each digit pushed and popped once.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — num='1432219', k=3 Values: 1432219, 3.
1stack=[]2for d in num:3 while k>0 and stack.top>d: pop; k--4 push d5remove leading zeros; drop remaining k from the endInput
- array
- [1432219, 3]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- num = "1432219", k = 3
- Output:
- "1219"
- Explanation:
- Drop 4,3,2 to get the smallest 1219.
Example 2
- Input:
- num = "10200", k = 1
- Output:
- "200"
- Explanation:
- Removing 1 gives 0200 → 200.
Example 3
- Input:
- num = "10", k = 2
- Output:
- "0"
- Explanation:
- Remove both digits → 0.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.