Practice › Stack & Queue
Remove K Digits
Medium · Stack & Queue · Asked at Amazon, Google, Microsoft, Adobe, Snapchat
Remove exactly k digits from the number num so that the remaining number is as small as possible. Print it without leading zeros; print 0 if nothing (or only zeros) remains.
Input
First line: num (digits, no leading zeros unless it is 0). Second line: k.
Output
The smallest possible number.
Constraints
- 1 ≤ k ≤ |num| ≤ 10^5
Greedy with a stack: while the previous digit is larger than the current one and removals remain, pop it. Remove any leftover k from the end.
Example 1
Input
1432219 3
Output
1219
Example 2
Input
10200 1
Output
200
Hints
- A smaller digit earlier in the number matters more than anything later.
- Scan left to right with a stack: while removals remain and the previous digit is larger than the current one, delete the previous digit.
Approach
Greedy with a monotonic stack: for each digit d, pop while k > 0 and the top is greater than d (removing a larger digit before a smaller one always makes the number smaller), then push d. If removals remain, the stack is non-decreasing, so remove from the end. Strip leading zeros; if nothing is left, the answer is "0".
Complexity: O(n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
string num;
int k;
cin >> num >> k;
string st;
for (char d : num) {
while (k > 0 && !st.empty() && st.back() > d) st.pop_back(), k--;
st.push_back(d);
}
while (k-- > 0) st.pop_back();
size_t i = 0;
while (i < st.size() && st[i] == '0') i++;
string res = st.substr(i);
cout << (res.empty() ? "0" : res) << "\n";
return 0;
}Python solution
import sys
data = sys.stdin.read().split()
num, k = data[0], int(data[1])
st = []
for d in num:
while k and st and st[-1] > d:
st.pop()
k -= 1
st.append(d)
if k:
st = st[:-k]
print("".join(st).lstrip("0") or "0")Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String num = sc.next();
int k = sc.nextInt();
StringBuilder st = new StringBuilder();
for (char d : num.toCharArray()) {
while (k > 0 && st.length() > 0 && st.charAt(st.length() - 1) > d) {
st.deleteCharAt(st.length() - 1);
k--;
}
st.append(d);
}
st.setLength(st.length() - k);
int i = 0;
while (i < st.length() && st.charAt(i) == '0') i++;
String res = st.substring(i);
System.out.println(res.isEmpty() ? "0" : res);
}
}