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.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.
This 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'.
C
C++
Java
C#
JavaScript
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.
Remove K digits | Build lowest number | Leetcode #402 • Techdose • 91,163 views views
Watch 9 more video solutions →Practice Remove K Digits with our built-in code editor and test cases.
Practice on FleetCode