Remove K Digits
A medium Stack problem included in Striver A2Z. Below: the roles whose interviews prioritise this topic, and how to practise it.
- Topic
- Stack
- Sheets
- 1
- Core for
- 8 roles
- Platform
- LeetCode
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-09High-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.
What each operation costs
| Operation | Time |
|---|---|
| push item onto the top | O(1) |
| pop item from the top | O(1) |
| inspect the topmost element | O(1) |
What usually goes wrong with Stack
- Popping from or peeking into an empty stack without first verifying that the size is positive, causing runtime null pointer or empty collection errors.
- Forgetting to verify that the stack is completely empty at the end of bracket matching, which mistakenly accepts strings with dangling unclosed opening symbols.
- Storing values instead of indices in monotonic stacks, making it impossible to calculate distance intervals between matching elements afterwards.
Which roles need this problem
Stack is a core topic for these 8 roles — if you're targeting one of them, this problem is early in your path, not optional.
Secondary for 9 more roles, including Frontend Engineer, Data Engineer, Game Developer.
Track this in your role's order
Pick your target role and all 370 problems — including this one — resequence to what that interview actually asks. Free.
Start freeMore Stack problems
Problem set and role mapping as of .