Remove K Digits
A medium Stack interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Stack
- Sheets
- 1
- Core for
- 9 roles
The problem
Given a string representing a non-negative integer and an integer k, remove k digits from the number so that the new number is the smallest possible. Return the result as a string. The result must not have leading zeros unless it is "0".
Example 1
- Input
- num = "1432219", k = 3
- Output
- "1219"
- Why
- Remove digits 4, 3, and 2 to get the smallest number 1219.
Example 2
- Input
- num = "10200", k = 1
- Output
- "200"
- Why
- Remove the leading 1 to get 0200, which becomes 200 after removing leading zeros.
Constraints
- 1 <= num.length <= 10^5
- num consists of only digits
- 0 <= k <= num.length
- num does not contain leading zeros except the number "0" itself
How to think about it
Updated 2026-09-29High-order digits outweigh all lower-order digits combined. Given two digits side by side, if `num[i] > num[i + 1]`, removing `num[i]` immediately drops the magnitude of the number far more than any removal further right could ever compensate for. The optimal sequence of removals greedily eliminates the first peak digit until removals run out.
Approaches, worst first
Greedy peak deletion with string splicing
time O(k * n) · space O(n)
Repeatedly find the first index where `num[i] > num[i + 1]`, splice that character out, decrement k, and repeat. Searching and splicing strings k times takes quadratic time, unviable for strings of length 10^5.
Monotonic increasing stack of digitsWrite this one
time O(n) · space O(n)
Iterate through the string. While `k > 0`, the stack is non-empty, and the current digit is strictly less than the stack top, pop the stack and decrement k. Push the current digit. If removals remain after the loop, pop the excess from the tail. Strip leading zeros and return.
Where people lose marks · 3
- Unused budget when digits are already monotonic: for an input like `"12345"` with `k = 2`, the inner loop never triggers; you must pop the trailing `k` digits from the end of the stack before converting to string.
- Residual leading zeros: stripping leading zeros must leave at least one digit when the number is zero, otherwise `"10"` with `k = 1` evaluates to empty string instead of `"0"`.
- Total erasure when `k == num.length`: the entire string is removed, and the output must be `"0"` rather than `""`.
The theory behind it
Stack — the ground this problem stands on. All Stack problems
What Stack is
A stack is a vertical pile of cafeteria trays where items enter and depart from one single opening at the top. The most recent item set down is the first one retrieved, while items deposited earlier remain buried underneath until newer arrivals are lifted away. This strict last-in, first-out sequence guarantees that older context stays preserved until all newer nested actions run to completion.
When to reach for it
Reach for a stack whenever an algorithm encounters nested structures like matched brackets, tags, or algebraic formulas. Problems demanding undo operations, function execution histories, or evaluating postfix arithmetic require this discipline. It is also the primary structure for monotonic queries where a task asks for the nearest greater or smaller value adjacent to each position in a series.
How the pattern works
Picture peeling layers back in exact reverse order of their arrival. Push items as pending jobs or unclosed delimiters encounter the scan. When closing boundaries appear, pop the topmost entry and check for compatibility. For monotonic patterns, maintain an invariant where elements on the stack remain strictly increasing or decreasing; pop any items that violate this rule before recording candidate answers and pushing the current item.
More Stack problems
Target Roles
Core requirement for 9 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .