Remove K Digits (LeetCode 402)
You are given a non-negative whole number written as a string of decimal digits, num, and a count k. Delete exactly k of its digits, leaving the others where they are relative to each other, so that the number that is left is as small as possible.
Return that number as a string, written the usual way: without leading zeros, and as "0" when no digit is left or only zeros are.
Worked Examples
num = "1432219", k = 3"1219"4, the 3 and one of the 2s leaves 1219; no other choice of three digits leaves a smaller number.num = "10200", k = 1"200"1 leaves the digits 0200, which is the number 200: the answer is written without its leading zero.num = "10", k = 2"0"0.⚖️Formal Constraints & Bounds
1 <= k <= num.length <= 105numconsists of only digits.numdoes not have any leading zeros except for the zero itself.
Core Insight
The leftmost place that changes decides which number is smaller, so a bigger digit sitting right before a smaller one is always worth deleting: a stack pops such digits while removals remain, and any removals left over come off the end.
Real-World Scenario & Production Applications
Identifiers, version strings and sort keys are compared the way numbers are, from the left: the first place that differs decides. Whenever a system must shorten such a sequence by a fixed number of characters and keep the rest in order (trimming a key to a length budget, sampling a sequence down), the best result spends every deletion on the earliest place it can lower, which is exactly what the pop-bigger stack does in one pass.
Step-by-Step Execution Trace Table
Example 2, num = "10200", k = 1 (the trap case: leading zeros):
digit | while k > 0 and stack and stack[-1] > digit | What the code does | stack after | k after |
|---|---|---|---|---|
1 | stack is empty: no | push 1 | ["1"] | 1 |
0 | "1" > "0": yes, then k is 0: no | pop 1, k -= 1, push 0 | ["0"] | 0 |
2 | k is 0: no | push 2 | ["0", "2"] | 0 |
0 | k is 0: no | push 0 | ["0", "2", "0"] | 0 |
0 | k is 0: no | push 0 | ["0", "2", "0", "0"] | 0 |
| after the loop | stack[:4 - 0] keeps every digit | ["0", "2", "0", "0"] | 0 | |
"0200".lstrip("0") gives "200": without it the answer would be "0200" |
return result or "0" gives "200".
| 1 | Numbers of the same length are compared from the left, so the earliest digit you can lower matters most: a bigger digit right before a smaller one is always worth deleting. |
| 2 | Keep a `stack` of the digits you keep. While `k > 0` it never decreases from bottom to top: before pushing `digit`, pop every `stack[-1] > digit` and spend one removal for each. |
| 3 | Loop `for digit in num:` with `while k > 0 and stack and stack[-1] > digit:` popping and doing `k -= 1`, then `stack.append(digit)`. After the loop, `stack = stack[:len(stack) - k]` spends the removals left over on the tail. |
| 4 | The trap: the number is written without leading zeros. Return `"".join(stack).lstrip("0") or "0"`: `"10200"` with `k = 1` leaves `"0200"`, which must be `"200"`, and an empty result is `"0"`. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Two numbers with the same number of digits are compared from the left: the first place where they differ decides. So when you must delete k digits, the digit to delete first is the one whose removal lowers the earliest place. The Lexicographic Stack finds those digits in one pass. It keeps the digits it wants on a stack; when a new digit is smaller than the digit on top and removals remain, the top digit goes, because the smaller digit then moves one place to the left. It keeps popping while that holds, and then pushes digit.
🧗 The Analogy: A Line of Climbers Sorted by Height
Climbers arrive one by one to form a rope team, and you may send k of them home, but never reorder them. You want the team to look as short as possible from the front. When a shorter climber arrives while a taller one stands just ahead, send the taller one home, and keep doing it while you still can: the shorter climber moves forward. When you run out of arrivals with home tickets left, the team already rises from front to back, so the tallest climbers are the last ones: send them home from the back.
🔑 Why It Works
A pop never has to be undone: once a smaller digit takes an earlier place, no set of later deletions can put a smaller digit there. The last line is the trap: the answer is a number, so it is written without leading zeros, and an empty result is "0".
Leading zeros and an empty result (the trap):
"".join(stack)can start with zeros or be empty: popping the1of"10200"leaves"0200". Strip them with.lstrip("0")andreturn result or "0", so the answers are"200"and, for"10"withk = 2,"0".Removals left over: when
numalready rises, as in"12345"withk = 2, the loop pops nothing. Cut the tail withstack[:len(stack) - k];stack[:-k]empties the stack whenkis 0.ifinstead ofwhile: one small digit may have to clear several bigger ones:"9991"withk = 3must pop all three9s and return"1", not"9".Popping equal digits: use
stack[-1] > digit, not>=:"1121"withk = 1must return"111"; popping the equal1wastes the removal and returns"121".Deleting digits one at a time: rescanning from the left for the first digit bigger than the one after it is correct but O(N · k), about
5 * 109steps at these limits; the stack does allkremovals in one pass.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Delete exactly k of its digits" to get a number "as small as possible", with the remaining digits kept in their order: a budget of deletions and a result that is compared from the left. The earliest place that changes decides the comparison, so each new digit should knock out the bigger digits in front of it while the budget lasts: the Lexicographic Stack.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision rule for each digit: while k > 0 and stack and stack[-1] > digit, pop and spend one removal; then push digit.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Keep
stacka list, not a string: popping withs = s[:-1]copies the whole string every time, which turns the pass quadratic on105digits.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use a Lexicographic Stack. Two numbers of the same length are compared from the left, so the earliest digit I can lower matters most. I walk the digits once and keep a stack of the digits I'm keeping. When the new digit is smaller than the top of the stack and I still have removals, I pop the top and spend one removal, and I keep popping while that holds; then I push the new digit. A bigger digit right before a smaller one is always the best deletion, so no pop ever has to be undone. If removals are left at the end, the stack never decreases, so I cut them off the tail. The trap is the output: I strip the leading zeros, and return zero if nothing is left. Each digit is pushed once and popped at most once, so it's
O(N)time andO(N)space.
Complexity & Mathematical Proof
O(N)
Look at the code: for digit in num runs N times, and each digit is pushed once by stack.append(digit). The inner while can pop several digits at one step, but every pop removes a digit that was pushed earlier, and a digit is popped at most once, so all the pops of the whole run add up to at most N (in fact at most k). The slice stack[:len(stack) - k], the join and lstrip("0") each walk at most N characters once. Total: O(N).
O(N)
stack holds at most N digits (all of them when nothing is popped), and the slice and the joined result are at most N characters each. Space: O(N), the returned string included.
T(N) = N pushes + at most N pops + O(N) to cut, join and strip = O(N)
Derivation Progression
N iterations
for digit in num reads each digit once and pushes it once with stack.append(digit).
at most N in total
Each pop removes a digit pushed earlier, and a digit is popped at most once, so the while runs at most N extra times over the whole run (and at most k times).
O(N)
stack[:len(stack) - k], "".join(stack) and .lstrip("0") each walk at most N characters.
O(N)
N pushes, at most N pops and three linear passes.
Variable Definitions
Number of digits, len(num) (at most 105)
Digits still to delete (at most N)
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(N): stack holds at most N digits
O(N): the returned string
Boundary Best / Worst Cases
: every digit is still read and pushed once, even when nothing is popped
: at most N pops in total, however they are spread over the digits
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "Delete exactly k of its digits", "as small as possible". A fixed budget of deletions, the rest kept in order, and a result compared from the left: the Lexicographic Stack, which pops a bigger item whenever a smaller one arrives and the budget allows.
digits and . Deleting one digit at a time with a rescan from the left is , about steps at ; the stack pushes each digit once and pops it at most once: time, memory.
On a stream, a digit that is pushed may still be popped by a later, smaller digit while the budget lasts, so nothing can be emitted before the budget is spent or the input ends: the stack is the buffer.
Core Algorithmic State Invariants
- The Budget Is the Only Brake
Without k > 0 the loop would pop until stack never decreases and could delete more digits than allowed. The budget is what stops it: once k reaches 0, every remaining digit is kept as it comes.
- Largest Instead of Smallest
Flip the comparison to stack[-1] < digit and the same pass keeps the largest possible number instead: a smaller digit in front of a bigger one is now the one to delete.
Remove K Digits (LeetCode 402)
You are given a non-negative whole number written as a string of decimal digits, num, and a count k. Delete exactly k of its digits, leaving the others where they are relative to each other, so that the number that is left is as small as possible.
Return that number as a string, written the usual way: without leading zeros, and as "0" when no digit is left or only zeros are.
Worked Examples
num = "1432219", k = 3"1219"4, the 3 and one of the 2s leaves 1219; no other choice of three digits leaves a smaller number.num = "10200", k = 1"200"1 leaves the digits 0200, which is the number 200: the answer is written without its leading zero.num = "10", k = 2"0"0.⚖️Formal Constraints & Bounds
1 <= k <= num.length <= 105numconsists of only digits.numdoes not have any leading zeros except for the zero itself.
Core Insight
The leftmost place that changes decides which number is smaller, so a bigger digit sitting right before a smaller one is always worth deleting: a stack pops such digits while removals remain, and any removals left over come off the end.
Real-World Scenario & Production Applications
Identifiers, version strings and sort keys are compared the way numbers are, from the left: the first place that differs decides. Whenever a system must shorten such a sequence by a fixed number of characters and keep the rest in order (trimming a key to a length budget, sampling a sequence down), the best result spends every deletion on the earliest place it can lower, which is exactly what the pop-bigger stack does in one pass.
Step-by-Step Execution Trace Table
Example 2, num = "10200", k = 1 (the trap case: leading zeros):
digit | while k > 0 and stack and stack[-1] > digit | What the code does | stack after | k after |
|---|---|---|---|---|
1 | stack is empty: no | push 1 | ["1"] | 1 |
0 | "1" > "0": yes, then k is 0: no | pop 1, k -= 1, push 0 | ["0"] | 0 |
2 | k is 0: no | push 2 | ["0", "2"] | 0 |
0 | k is 0: no | push 0 | ["0", "2", "0"] | 0 |
0 | k is 0: no | push 0 | ["0", "2", "0", "0"] | 0 |
| after the loop | stack[:4 - 0] keeps every digit | ["0", "2", "0", "0"] | 0 | |
"0200".lstrip("0") gives "200": without it the answer would be "0200" |
return result or "0" gives "200".
| 1 | Numbers of the same length are compared from the left, so the earliest digit you can lower matters most: a bigger digit right before a smaller one is always worth deleting. |
| 2 | Keep a `stack` of the digits you keep. While `k > 0` it never decreases from bottom to top: before pushing `digit`, pop every `stack[-1] > digit` and spend one removal for each. |
| 3 | Loop `for digit in num:` with `while k > 0 and stack and stack[-1] > digit:` popping and doing `k -= 1`, then `stack.append(digit)`. After the loop, `stack = stack[:len(stack) - k]` spends the removals left over on the tail. |
| 4 | The trap: the number is written without leading zeros. Return `"".join(stack).lstrip("0") or "0"`: `"10200"` with `k = 1` leaves `"0200"`, which must be `"200"`, and an empty result is `"0"`. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Two numbers with the same number of digits are compared from the left: the first place where they differ decides. So when you must delete k digits, the digit to delete first is the one whose removal lowers the earliest place. The Lexicographic Stack finds those digits in one pass. It keeps the digits it wants on a stack; when a new digit is smaller than the digit on top and removals remain, the top digit goes, because the smaller digit then moves one place to the left. It keeps popping while that holds, and then pushes digit.
🧗 The Analogy: A Line of Climbers Sorted by Height
Climbers arrive one by one to form a rope team, and you may send k of them home, but never reorder them. You want the team to look as short as possible from the front. When a shorter climber arrives while a taller one stands just ahead, send the taller one home, and keep doing it while you still can: the shorter climber moves forward. When you run out of arrivals with home tickets left, the team already rises from front to back, so the tallest climbers are the last ones: send them home from the back.
🔑 Why It Works
A pop never has to be undone: once a smaller digit takes an earlier place, no set of later deletions can put a smaller digit there. The last line is the trap: the answer is a number, so it is written without leading zeros, and an empty result is "0".
Leading zeros and an empty result (the trap):
"".join(stack)can start with zeros or be empty: popping the1of"10200"leaves"0200". Strip them with.lstrip("0")andreturn result or "0", so the answers are"200"and, for"10"withk = 2,"0".Removals left over: when
numalready rises, as in"12345"withk = 2, the loop pops nothing. Cut the tail withstack[:len(stack) - k];stack[:-k]empties the stack whenkis 0.ifinstead ofwhile: one small digit may have to clear several bigger ones:"9991"withk = 3must pop all three9s and return"1", not"9".Popping equal digits: use
stack[-1] > digit, not>=:"1121"withk = 1must return"111"; popping the equal1wastes the removal and returns"121".Deleting digits one at a time: rescanning from the left for the first digit bigger than the one after it is correct but O(N · k), about
5 * 109steps at these limits; the stack does allkremovals in one pass.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Delete exactly k of its digits" to get a number "as small as possible", with the remaining digits kept in their order: a budget of deletions and a result that is compared from the left. The earliest place that changes decides the comparison, so each new digit should knock out the bigger digits in front of it while the budget lasts: the Lexicographic Stack.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision rule for each digit: while k > 0 and stack and stack[-1] > digit, pop and spend one removal; then push digit.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Keep
stacka list, not a string: popping withs = s[:-1]copies the whole string every time, which turns the pass quadratic on105digits.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use a Lexicographic Stack. Two numbers of the same length are compared from the left, so the earliest digit I can lower matters most. I walk the digits once and keep a stack of the digits I'm keeping. When the new digit is smaller than the top of the stack and I still have removals, I pop the top and spend one removal, and I keep popping while that holds; then I push the new digit. A bigger digit right before a smaller one is always the best deletion, so no pop ever has to be undone. If removals are left at the end, the stack never decreases, so I cut them off the tail. The trap is the output: I strip the leading zeros, and return zero if nothing is left. Each digit is pushed once and popped at most once, so it's
O(N)time andO(N)space.
Complexity & Mathematical Proof
O(N)
Look at the code: for digit in num runs N times, and each digit is pushed once by stack.append(digit). The inner while can pop several digits at one step, but every pop removes a digit that was pushed earlier, and a digit is popped at most once, so all the pops of the whole run add up to at most N (in fact at most k). The slice stack[:len(stack) - k], the join and lstrip("0") each walk at most N characters once. Total: O(N).
O(N)
stack holds at most N digits (all of them when nothing is popped), and the slice and the joined result are at most N characters each. Space: O(N), the returned string included.
T(N) = N pushes + at most N pops + O(N) to cut, join and strip = O(N)
Derivation Progression
N iterations
for digit in num reads each digit once and pushes it once with stack.append(digit).
at most N in total
Each pop removes a digit pushed earlier, and a digit is popped at most once, so the while runs at most N extra times over the whole run (and at most k times).
O(N)
stack[:len(stack) - k], "".join(stack) and .lstrip("0") each walk at most N characters.
O(N)
N pushes, at most N pops and three linear passes.
Variable Definitions
Number of digits, len(num) (at most 105)
Digits still to delete (at most N)
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(N): stack holds at most N digits
O(N): the returned string
Boundary Best / Worst Cases
: every digit is still read and pushed once, even when nothing is popped
: at most N pops in total, however they are spread over the digits
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "Delete exactly k of its digits", "as small as possible". A fixed budget of deletions, the rest kept in order, and a result compared from the left: the Lexicographic Stack, which pops a bigger item whenever a smaller one arrives and the budget allows.
digits and . Deleting one digit at a time with a rescan from the left is , about steps at ; the stack pushes each digit once and pops it at most once: time, memory.
On a stream, a digit that is pushed may still be popped by a later, smaller digit while the budget lasts, so nothing can be emitted before the budget is spent or the input ends: the stack is the buffer.
Core Algorithmic State Invariants
- The Budget Is the Only Brake
Without k > 0 the loop would pop until stack never decreases and could delete more digits than allowed. The budget is what stops it: once k reaches 0, every remaining digit is kept as it comes.
- Largest Instead of Smallest
Flip the comparison to stack[-1] < digit and the same pass keeps the largest possible number instead: a smaller digit in front of a bigger one is now the one to delete.