Introduction
LeetCode 402 Remove K Digits is one of those problems where the brute force solution feels obvious but completely falls apart at scale — and the optimal solution requires a genuinely clever insight that, once you see it, feels like magic.
This problem sits at the intersection of two powerful techniques — Greedy thinking and Monotonic Stack. If you have already solved Next Greater Element and Asteroid Collision, you have all the building blocks you need. This is where those patterns level up.
You can find the problem here — LeetCode 402 Remove K Digits.
What Is the Problem Really Asking?
You are given a number as a string and an integer k. Remove exactly k digits from the number such that the resulting number is as small as possible. Return it as a string without leading zeros.
Example:
num = "1432219",k = 3- We want to remove 3 digits to make the number as small as possible
- Remove
4,3,2→ remaining is"1219" - Output:
"1219"
Simple goal — smallest possible number after exactly k removals.
Real Life Analogy — Choosing the Best Price Tag
Imagine you are reading a price tag digit by digit from left to right. Every time you see a digit that is bigger than the next one coming, you have a chance to remove it and make the price smaller. You have a limited number of removals — use them wisely on the biggest offenders from the left side, because leftmost digits have the most impact on the overall value.
Removing a 9 from the front of a number shrinks it far more than removing a 9 from the end. This left-to-right priority with greedy removal is the entire insight of this problem.
The Core Greedy Insight
Here is the key question — which digit should we remove first to make the number as small as possible?
Think about it this way. In the number "1432219", which digit is hurting us the most? It is 4 — because it is large and sits early in the number. After removing 4 we get "132219". Now 3 is the biggest early offender. And so on.
More precisely — whenever you see a digit that is greater than the digit immediately after it, removing it makes the number smaller. This is because a larger digit sitting before a smaller digit inflates the overall value.
This is the Greedy rule: scan left to right, and whenever the current digit on the stack is greater than the incoming digit, remove it (if we still have removals left).
A Monotonic Increasing Stack enforces exactly this — it keeps digits in non-decreasing order, automatically kicking out any digit that is larger than what comes next.
The Solution — Monotonic Stack
Step-by-Step Dry Run — num = "1432219", k = 3
Processing 1: Stack empty → push. Stack: [1]
Processing 4: Stack top 1 < 4 → no pop. Push 4. Stack: [1, 4]
Processing 3: Stack top 4 > 3 and k=3 → pop 4, k=2. Stack: [1] Stack top 1 < 3 → stop. Push 3. Stack: [1, 3]
Processing 2: Stack top 3 > 2 and k=2 → pop 3, k=1. Stack: [1] Stack top 1 < 2 → stop. Push 2. Stack: [1, 2]
Processing 2: Stack top 2 == 2 → not greater, stop. Push 2. Stack: [1, 2, 2]
Processing 1: Stack top 2 > 1 and k=1 → pop 2, k=0. Stack: [1, 2] k=0, stop. Push 1. Stack: [1, 2, 1]
Processing 9: k=0, no more removals. Push 9. Stack: [1, 2, 1, 9]
k is now 0, skip the cleanup loop.
Build result: pop all → "9121" → reverse → "1219" No leading zeros. Return "1219" ✅
Step-by-Step Dry Run — num = "10200", k = 1
Processing 1: stack empty → push. Stack: [1]
Processing 0: Stack top 1 > 0 and k=1 → pop 1, k=0. Stack: [] Push 0. Stack: [0]
Processing 2: k=0, no removals. Push. Stack: [0, 2]
Processing 0: k=0. Push. Stack: [0, 2, 0]
Processing 0: k=0. Push. Stack: [0, 2, 0, 0]
k=0, skip cleanup.
Build result: "0020" → reverse → "0200" Remove leading zero → "200" Return "200" ✅
Step-by-Step Dry Run — num = "10", k = 2
Processing 1: push. Stack: [1]
Processing 0: Stack top 1 > 0 and k=2 → pop 1, k=1. Stack: [] Push 0. Stack: [0]
k=1 remaining → cleanup loop → pop 0, k=0. Stack: []
Build result: empty string. Remove leading zeros: nothing to remove. Length is 0 → return "0" ✅
The Three Tricky Cases You Must Handle
Case 1 — k is not fully used after the loop This happens with a non-decreasing number like "12345" with k=2. No element ever gets popped during the loop because no digit is greater than the next one. The stack ends up as [1,2,3,4,5] with k still = 2. The solution is to pop from the top of the stack — which holds the largest digits — until k hits 0.
Case 2 — Leading zeros After removing digits, the remaining number might start with zeros. "10200" becomes "0200" after removing 1. We strip leading zeros with a while loop. But we must be careful not to strip the only zero — that is why we check length > 0 before each removal.
Case 3 — Empty result If all digits are removed (like "10" with k=2), the StringBuilder ends up empty. We return "0" because an empty number is represented as zero.
Why Remaining k Gets Removed From the End
After the main loop, if k is still greater than 0, why do we remove from the top of the stack (which corresponds to the end of the number)?
Because the stack at this point holds a non-decreasing sequence. In a non-decreasing sequence, the largest values are at the end. Removing from the end removes the largest remaining digits — which is exactly the greedy choice to minimize the number.
For example in "12345" with k=2: the stack is [1,2,3,4,5]. Pop top twice → remove 5 and 4 → [1,2,3] → result is "123". Correct!
Time and Space Complexity
Time Complexity: O(n) — each digit is pushed onto the stack exactly once and popped at most once. Even with the while loop inside the for loop, total push and pop operations across the entire run never exceed 2n. The leading zero removal is also O(n) in the worst case. Overall stays linear.
Space Complexity: O(n) — the stack holds at most n digits in the worst case when no removals happen during the main loop.
Common Mistakes to Avoid
Not handling remaining k after the loop This is the most common mistake. If the number is already non-decreasing, the loop never pops anything. Forgetting the cleanup loop gives the wrong answer for inputs like "12345" with k=2.
Not removing leading zeros After removals, the result might start with zeros. "0200" should be returned as "200". Skipping this step gives wrong output.
Returning empty string instead of "0" When all digits are removed, return "0" not "". An empty string is not a valid number representation.
Using >= instead of > in the pop condition If you pop on equal digits too, you remove more than necessary and might get wrong results. Only pop when strictly greater — equal digits in sequence are fine to keep.
How This Connects to the Monotonic Stack Series
Looking at the stack problems you have been solving:
496 Next Greater Element — monotonic decreasing stack, find first bigger to the right 735 Asteroid Collision — stack simulation, chain reactions 402 Remove K Digits — monotonic increasing stack, greedy removal for minimum number
The direction of the monotonic stack flips based on what you are optimizing. For "next greater" you keep a decreasing stack. For "smallest number" you keep an increasing stack. Recognizing which direction to go is the skill that connects all these problems.
FAQs — People Also Ask
Q1. Why does a Monotonic Stack give the smallest number in LeetCode 402? A monotonic increasing stack ensures that at every point, the digits we have kept so far are in the smallest possible order. Whenever a smaller digit arrives and the stack top is larger, removing that larger digit can only make the number smaller — this greedy choice is always optimal.
Q2. What happens if k is not fully used after the main loop in LeetCode 402? The number is already in non-decreasing order so no removals happened during the loop. The remaining removals should be made from the end of the number (top of stack) since those are the largest values in a non-decreasing sequence.
Q3. How are leading zeros handled in LeetCode 402? After building the result string, strip any leading zeros with a while loop. If stripping leaves an empty string, return "0" because the empty case represents zero.
Q4. What is the time complexity of LeetCode 402? O(n) time because each digit is pushed and popped at most once across the entire algorithm. Space complexity is O(n) for the stack.
Q5. Is LeetCode 402 asked in coding interviews? Yes, it is frequently asked at companies like Google, Amazon, and Microsoft. It tests greedy thinking combined with monotonic stack — two patterns that interviewers love because they require genuine insight rather than memorization.
Similar LeetCode Problems to Practice Next
- 496. Next Greater Element I — Easy — monotonic decreasing stack
- 739. Daily Temperatures — Medium — next greater with distances
- 316. Remove Duplicate Letters — Medium — similar greedy stack with constraints
- 1081. Smallest Subsequence of Distinct Characters — Medium — same approach as 316
- 84. Largest Rectangle in Histogram — Hard — advanced monotonic stack
Conclusion
LeetCode 402 Remove K Digits is a beautiful problem that rewards clear thinking. The greedy insight — always remove a digit when a smaller digit comes after it — naturally leads to the monotonic stack solution. The three edge cases (remaining k, leading zeros, empty result) are what separate a buggy solution from a clean, accepted one.
Work through all three dry runs carefully. Once you see how the stack stays increasing and how each pop directly corresponds to a greedy removal decision, this pattern will click permanently and carry you through harder stack problems ahead.
