Python solution with detailed explanation


  • 0
    G

    Solution

    Remove K Digits https://leetcode.com/problems/remove-k-digits/

    • Examples which are interesting: "1234567", "7654321". The first is strictly increasing and the second is strictly decreasing.
    • How do you choose to remove the first element?
    • You will scan from left to right and remove the first peak element. Example 1 that would be 7, the last element. Example 2 that would be 7, the first
      element. Why the first peak element? You want to remove the first largest element from left which has a smaller element on right, so that the smaller element can fill in for the large element that we removed. You will repeat this process k times and have a complexity of O(K * N). https://discuss.leetcode.com/topic/59871/two-algorithms-with-detailed-explaination
    • Now how can we do the above efficiently? We can use a stack to simulate this.
    • if x > st[-1], push x. If x < st[-1], pop all elements from the stack which are greater than x while making sure we do not pop more than a total of k elements.
    • Adjust for boundary conditions.
            for x in num:
                while k and st and x < st[-1]:
                    st.pop()
                    k = k-1
                st.append(x)
    

    Solution Code

    class Solution(object):
        def removeKdigits(self, num, k):
            """
            :type num: str
            :type k: int
            :rtype: str
            """
            st = []
            for x in num:
                while k and st and x < st[-1]:
                    st.pop()
                    k = k-1
                st.append(x)
            while st and k > 0:
                st.pop()
                k = k-1
            i = 0
            while i < len(st) and st[i] == "0":
                i = i+1
            if len(st[i:]) == 0:
                return "0"
            else:
                return "".join(st[i:])
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.