Coding · Stacks
Smallest number after removing k digits
- Reported in several places
- Medium
- SDE (2-5 years)
- 2 sources
Two or more independent public pages, at least one a candidate write-up.
Solve it in the playground, with tests
Given a string of digits that represents a non-negative integer and a count k, delete exactly k digits so that the remaining number is as small as possible, and return it as a string with no leading zeros, or 0 if nothing is left. The remaining digits keep their original order. For 1432219 and k = 3 the answer is 1219. The input can have up to 100,000 digits, so the result cannot be handled as a native integer. Two candidate reports list it, one in the data structures round of an SDE interview and one under the second round of an onsite loop in October 2025.
Restated in our own words, not a quote from PhonePe or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would clarify the input and the output. Is the number given as a string of digits, possibly up to 100,000 long? Can the input have leading zeros? Must exactly k digits be removed, and is k always at most the length? Should the result keep leading zeros or drop them, and what is returned when nothing is left? Do the remaining digits keep their original order?
My assumptions: a digit string with no leading zeros, exactly k deletions with k at most the length, remaining digits in order, leading zeros stripped from the result, and 0 when nothing remains. Because the string is long, I treat it as text and never convert it to a number.
Brute force
Say the obvious answer and why it is too slow.
Try every way to delete k digits: choose which n-k positions to keep, build each candidate string, and take the smallest. Candidates have the same length, so comparing them as strings gives the numeric order. This is correct, but there are C(n, k) choices, which for 20 digits and k = 10 is already 184,756 and for realistic inputs is astronomical.
A smarter loop removes one digit k times: each time scan for the first digit that is larger than the digit after it and delete that one, or delete the last digit if none exists. That is correct and it is the idea behind the final solution, but each of the k rounds rescans the string, so it costs O(n * k), which is billions of steps for n = 100,000 and k near half of n.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(C(n, k)) subsets, or O(n * k) deleting one digit per pass
- Time
- O(n) for n digits
- Space
- O(n) for the stack
The pattern is a monotonic stack with a deletion budget. For numbers of equal length, the leftmost position where they differ decides which is smaller, so the left end matters most. When is deleting a digit most valuable? When it is larger than the digit right after it: deleting it slides a smaller digit into its place, lowering the number at the earliest possible position. If no digit is larger than its successor, the digits are non-decreasing, and the best deletion is the last digit.
The stack applies this in one pass. Scan the digits left to right, keeping a stack of kept digits. For each new digit, while deletions remain and the top of the stack is larger than the new digit, pop the top and spend one deletion; then push the new digit. The stack is therefore non-decreasing until the budget runs out. After the scan, any deletions left over come off the end, which holds the largest digits of a non-decreasing stack. Finally strip leading zeros and return 0 if nothing remains.
Why popping is safe: suppose the top t is larger than the incoming digit d and a deletion is still available. Any plan that keeps both t and d, and spends a deletion somewhere later, gets a smaller number by moving that deletion onto t, because the digit in t's place becomes d or something no larger than d, and nothing before that place changes. A plan that keeps t but deletes d is beaten by swapping the two. Earlier positions are settled first, so the rule holds by induction. Equal digits are not popped because popping gains nothing. Each digit is pushed once and popped at most once, so time is O(n), and the stack takes O(n) space. Out loud: "monotonic stack, pop while the previous digit is bigger and I still have deletions, trim the tail, strip zeros."
Walk it through
A dry run on the example, step by step.
| Digit | Popped | Stack after | k left |
|---|---|---|---|
| 1 | none | 1 | 3 |
| 4 | none | 14 | 3 |
| 3 | 4 | 13 | 2 |
| 2 | 3 | 12 | 1 |
| 2 | none | 122 | 1 |
| 1 | 2 | 121 | 0 |
| 9 | none | 1219 | 0 |
| end | none | 1219 | 0 |
Take 1432219 and k = 3. The 1 is pushed. The 4 is larger than 1, so it is pushed. The 3 is smaller than the top 4, so 4 is popped and k drops to 2, then 3 is pushed. The 2 pops the 3 (k becomes 1) and is pushed. The next 2 equals the top, so nothing is popped and it is pushed. The 1 pops one 2 (k becomes 0) and is pushed. The 9 is pushed with no budget left.
The budget is spent, so the stack 1219 is the answer, and it has no leading zeros. Compare it with simply removing the three largest digits, which would give 1221: the stack found the smaller 1219 because the deletions were spent where a big digit sat before a small one.
The code
Runnable JavaScript, checked against test cases.
function removeKdigits(num, k) {
if (k >= num.length) return "0";
const stack = [];
for (const digit of num) {
while (k > 0 && stack.length > 0 && stack[stack.length - 1] > digit) {
stack.pop();
k--;
}
stack.push(digit);
}
while (k > 0) {
stack.pop();
k--;
}
let start = 0;
while (start < stack.length - 1 && stack[start] === "0") start++;
return stack.slice(start).join("");
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
When k is zero the digits are unchanged. When k equals the length everything is deleted and the answer is 0, handled before the scan. A result with leading zeros, like 10200 with k = 1 giving 0200, is stripped to 200, and one that is all zeros collapses to a single 0.
- Increasing digits: nothing is popped during the scan, and the leftover budget trims the end.
- Decreasing digits: every new digit pops the previous one until the budget is spent, so the front is deleted.
- Equal digits: nothing is popped, and the trim at the end removes copies from the tail.
- A single digit: k is 0 or 1, and both are handled.
- Zeros inside: 1002 with k = 1 pops the 1 and gives 002, stripped to 2.
Follow-ups to expect
Where the interviewer pushes next.
- How would you prove the greedy choice correct?
- What changes if you need the largest possible number instead?
- Can you do it with O(1) extra space, and what does your language allow?
- How does the same stack idea solve the smallest subsequence of distinct letters problem?
Where candidates slip
The mistakes this problem punishes.
The frequent mistake is using if instead of while when popping, which pops at most one digit per new digit. For 1562 with k = 2 the 2 must pop both 6 and 5 to reach 12, but with if the 5 stays and the answer comes out as 15.
Others: not trimming the leftover deletions from the end, so 12345 with k = 2 stays unchanged; forgetting to strip leading zeros, or returning an empty string instead of 0; stripping zeros before applying the deletions; converting to a number and losing digits past about 15; and popping on equal digits for no gain, which is harmless here but muddles the proof.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.