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.The key idea behind #402 Remove K Digits is to build the smallest possible number after removing exactly k digits. A common and efficient strategy uses a greedy approach combined with a monotonic stack. As you scan the digits from left to right, you maintain a stack that keeps digits in increasing order.
If the current digit is smaller than the digit at the top of the stack and you still have removals left (k > 0), removing the larger digit will produce a smaller overall number. This greedy decision ensures the resulting number remains minimal. Continue this process while maintaining the stack structure.
After processing all digits, you may still need to remove remaining digits, which are typically taken from the end of the stack. Finally, construct the result while handling edge cases such as leading zeros or an empty result.
This method efficiently processes each digit once, making it suitable for large inputs while maintaining optimal performance.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy with Monotonic Stack | O(n) | O(n) |
Techdose
This approach uses a stack to build the smallest possible number. We iterate over each digit in the string, and for each digit, we compare it with the top of the stack (if the stack is not empty). If the current digit is smaller than the top of the stack and we still have digits to remove, we pop from the stack. Finally, after the loop, if there are remaining digits to remove, we simply remove them from the end of the constructed stack. This ensures the smallest possible arrangement of the remaining digits.
Time Complexity: O(n), where n is the number of digits in num, because each digit is processed at most twice (once pushed and once popped).
Space Complexity: O(n), because of the space required for the stack to hold the digits.
1def removeKdigits(num: str, k: int) -> str:
2 stack = []
3 for digit in num:
4 whileThis Python implementation utilizes a stack to keep track of the most desirable sequence of digits. As the function iterates over each digit, it determines whether the stack should pop any elements based on whether doing so would create a smaller number. After the loop, any remaining digits are removed by slicing off the end of the stack. Leading zeros are removed from the final result, and if this leads to an empty string, we return '0'.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Remove K Digits is a popular interview problem that tests greedy thinking, stack usage, and string manipulation. Variations of this problem are commonly asked in technical interviews at large tech companies.
The optimal approach uses a greedy strategy with a monotonic stack. By removing larger digits when a smaller digit appears and k removals are still allowed, you ensure the resulting number is as small as possible. Each digit is processed once, making the approach efficient.
The greedy choice works because removing a larger digit before a smaller upcoming digit always leads to a smaller overall number. Making this decision locally at each step ensures the global minimum number after exactly k removals.
A stack is the most suitable data structure for this problem. It helps maintain digits in increasing order while allowing efficient removal of previously added digits when a smaller digit appears.