402. Remove K Digits (Python)

Related Topic

Stack. Greedy.

Description

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Sample I/O

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.

Note

1. The length of num is less than 10002 and will be ≥ k.
2. The given num does not contain any leading zero.

Methodology

Use stack to store the temperoray digit from num. If the current digit is smaller than top of stack, then we pop the stack until the top is greater or equal to the current digit.In the meanwhile k will keep updating, once k reach to 0, return the new string. After iteration, if the k is not 0, then we start to pop from stack until the k == 0. This method use stack and greedy, leetcode has very good explaination about this question. However I did a little improvement that when k == 0, stop iteration and appending. This will make performance a little better.

stack + greedy standard solution

    def removeKdigits(self, num: str, k: int) -> str:
        size = len(num)
        if size == k: return '0'
        stack = []
        for n in num:
            while stack and k and stack[-1] > int(n):
                stack.pop()
                k -= 1
            if len(stack) == 1 and stack[-1] == 0:# not leading 0
                stack.pop()
            stack.append(int(n))
        while k:
            stack.pop()
            k -= 1
        return ''.join(map(str,stack))  

BigO

Time complexity : O(N). Although there are nested loops, the inner loop is bounded to be run at most kk times globally. Together with the outer loop, we have the exact (N + k)(N+k) number of operations.

stack + greedy improved solution

    def removeKdigits(self, num: str, k: int) -> str:
        size = len(num)
        if size == k: return '0'
        stack = []
        for i, n in enumerate(num):
            while stack and k and stack[-1]>n:
                stack.pop()
                k-=1
            stack.append(n)
            if len(stack)==1 and stack[-1] == '0': 
                stack.pop()
            if not k:
                res = ''.join(stack)+num[i+1:]
                return res if res else '0'
        while k:
            stack.pop()
            k-=1
        return ''.join(stack)

BigO

Time complexity : O(N). Although there are nested loops, the inner loop is bounded to be run at most kk times globally. Together with the outer loop, we have the exact (N + k)(N+k) number of operations.