Watch 10 video solutions for Remove K Digits, a medium level problem involving String, Stack, Greedy. This walkthrough by Techdose has 91,163 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.
Example 1:
Input: num = "1432219", k = 3 Output: "1219" Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
Example 2:
Input: num = "10200", k = 1 Output: "200" Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
Example 3:
Input: num = "10", k = 2 Output: "0" Explanation: Remove all the digits from the number and it is left with nothing which is 0.
Constraints:
1 <= k <= num.length <= 105num consists of only digits.num does not have any leading zeros except for the zero itself.Problem Overview: You receive a numeric string num and an integer k. Remove exactly k digits so the resulting number is as small as possible while preserving the relative order of the remaining digits. Leading zeros must be handled carefully, and if all digits are removed the result should be "0".
Approach 1: Brute Force Digit Removal (Exponential time, O(2^n) time, O(n) space)
The naive strategy explores all ways to remove k digits and keeps the smallest resulting number. You recursively choose whether to remove or keep each digit until exactly k removals are made. After constructing each candidate string, normalize leading zeros and compare it against the current minimum. This approach demonstrates the core goal of minimizing the number but quickly becomes impractical because the number of combinations grows exponentially. It only works for very small inputs and mainly serves as a conceptual baseline.
Approach 2: Greedy Monotonic Stack (Optimal) (O(n) time, O(n) space)
The optimal strategy uses a greedy rule: remove digits that create a larger prefix. If a digit is bigger than the next one, deleting it makes the number smaller. A monotonic stack captures this idea efficiently. Iterate through the digits of num. While the stack is not empty, the current digit is smaller than the top of the stack, and you still have removals left (k > 0), pop the stack. This removes a larger digit that would otherwise increase the final number.
Push each processed digit onto the stack. After the scan, if k removals remain, remove digits from the end since the suffix is the largest remaining portion. Finally, build the result string from the stack and trim leading zeros. If the string becomes empty, return "0". The stack effectively maintains digits in increasing order, making this a classic combination of greedy, stack, and string processing techniques.
Recommended for interviews: Interviewers expect the monotonic stack solution. It shows you recognize the greedy property: removing a larger digit before a smaller one always improves the number. The brute force idea proves you understand the objective, but the stack-based O(n) solution demonstrates strong algorithmic thinking and familiarity with monotonic data structures.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Digit Removal | O(2^n) | O(n) | Conceptual understanding or very small inputs |
| Greedy Monotonic Stack | O(n) | O(n) | Optimal approach for large inputs and interview settings |