Remove K Digits
Mahabharata — The Treasurer's Reduction — Remove K Warriors to Leave the Smallest Force
क-संख्यकान् दूरीकृत्य — न्यूनतमं संख्यां रक्षेत्। उचितान् स्थानेषु — न्यूनतमः अंकः प्रथमम्॥
*Removing k from the count — preserve the smallest possible number. The smallest digit at each position — that is the goal.*
The Story
Given a string of digits and integer k, remove k digits to make the remaining number as small as possible.
For `num = "1432219"`, k=3: remove 4, 3, 2 → `"1219"`. Answer: `"1219"`. For `num = "10200"`, k=1: remove 1 → `"0200"` → `"200"` (strip leading zero). Answer: `"200"`.
The key insight is **greedy with a monotone increasing stack:** - We want the SMALLEST possible number - A number is smaller if its LEFTMOST digit is smaller - So: whenever we see a digit that is SMALLER than the previous digit, we should REMOVE the previous (larger) digit
This naturally leads to maintaining a monotone INCREASING stack: - For each digit: while k > 0 AND stack is non-empty AND stack.top > current digit → pop (remove the top, k--) - Push current digit
Trace `"1432219"`, k=3: - '1': push. stack=[1] - '4': 1<4. push. stack=[1,4] - '3': 4>3, k=3>0 → pop 4, k=2. 1<3. push. stack=[1,3] - '2': 3>2, k=2>0 → pop 3, k=1. 1<2. push. stack=[1,2] - '2': 2==2. push. stack=[1,2,2] - '1': 2>1, k=1>0 → pop 2, k=0. push 1. stack=[1,2,1] - '9': k=0, stop popping. push. stack=[1,2,1,9]
Wait — that gives 4 digits. We need n-k = 7-3 = 4 digits. But the expected answer is "1219"...
Let me retrace: - stack=[1], push 4: [1,4] - pop 4 (k=2), push 3: [1,3] - pop 3 (k=1), push 2: [1,2] - push 2: [1,2,2] - pop 2 (k=0), push 1: [1,2,1] - push 9: [1,2,1,9]
Result: "1219" ✓
Post-process: remove leading zeros. If empty → "0".
If k > 0 after processing all digits: remove k more from the end (the stack is increasing, so tail is largest).
The Brute Force Minimizer
Try all C(n,k) combinations of removing k digits. Return the minimum. Exponential time.
// Too slow for large inputs, shown for concept
public String removeKdigitsBruteForce(String num, int k) {
if (k >= num.length()) return "0";
String min = num;
for (int mask = 0; mask < (1<<num.length()); mask++) {
if (Integer.bitCount(mask) != k) continue;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < num.length(); i++)
if ((mask & (1<<i)) == 0) sb.append(num.charAt(i));
String s = sb.toString().replaceAll("^0+", "");
if (s.isEmpty()) s = "0";
if (s.compareTo(min) < 0) min = s;
}
return min;
}The Greedy Monotone Stack Wisdom
public String removeKdigits(String num, int k) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : num.toCharArray()) {
// Greedy: remove larger digits before current
while (k > 0 && !stack.isEmpty() && stack.peek() > c) {
stack.pop();
k--;
}
stack.push(c);
}
// If k remains, remove from the end (largest remaining)
while (k-- > 0) stack.pop();
// Build result, skip leading zeros
StringBuilder sb = new StringBuilder();
boolean leadingZero = true;
while (!stack.isEmpty()) {
char[] arr = stack.toArray(new char[0]);
// Stack is reversed, so iterate from end
for (int i = arr.length-1; i >= 0; i--) {
if (leadingZero && arr[i] == '0') continue;
leadingZero = false;
sb.append(arr[i]);
}
break;
}
return sb.length() == 0 ? "0" : sb.toString();
}Step-by-Step Walkthrough
num="5", k=1 '5': stack=[5]. k=1>0 but no previous. k=1: pop 5. stack=[]. k=0. Return "0" ✅
Deep Insight
**Why greedy works?** In any number, a digit at position i dominates a digit at position i+1 by a factor of 10. So having a smaller digit earlier ALWAYS results in a smaller number, regardless of what follows.
**The 'remaining k' case:** If we process all digits without using all k removals (e.g., `"123"`, k=2 — already sorted, nothing to pop), we have a monotone increasing stack. Remove from the END (largest digits): `"123"` → remove 3, 2 → `"1"`. The tail of a monotone increasing sequence is always largest.
**Leading zero handling:** After building the string, strip `0` prefixes. If all digits were removed or only zeros remain → return `"0"`.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(2^n) | O(n) | All subsets |
| Optimal | O(n) | O(n) | Each digit pushed/popped at most once |
Pattern Recognition
✅ Remove k digits for smallest number ✅ Greedy: monotone INCREASING stack ✅ Pop when top > current AND k > 0 ✅ Remaining k → remove from tail ✅ Strip leading zeros; empty → "0" **LeetCode Trigger Phrases:** → "remove k digits" for smallest number → "minimum possible integer after k removals" → Greedy + monotone stack for digit/element selection
Bhagavad Gita 3.42
इन्द्रियाणि पराण्याहुरिन्द्रियेभ्यः परं मनः। मनसस्तु परा बुद्धिर्यो बुद्धेः परतस्तु सः॥
The senses are superior to the gross body; the mind is superior to the senses; the intellect is superior to the mind; and the Self is superior even to the intellect.
Connection: The greedy algorithm models a hierarchy of preference — at each position, a smaller digit is always preferred to a larger one. Like the Gita's hierarchy where higher faculties govern lower ones, the algorithm immediately removes any digit that is 'inferior' (larger, causing a bigger number) when a 'superior' (smaller) digit arrives. The monotone increasing stack embodies this hierarchy: each element proves its right to stay by being no greater than what follows.