Greedy O(n) solution with thought process 🔥 | Clean code with explanation ✅ | Python3
Intuition\nWe would want to start making a couple observations about the nature of the problem, and what it takes to minimize the number after removal.\n\nFirst
# Intuition\nWe would want to start making a couple observations about the nature of the problem, and what it takes to minimize the number after removal.\n\nFirst, we observe that if we have a sorted ordering of digits already, eg 12445, we can just remove k elements from the right for lowest value.\n\nBut if we have peaks in digits such as 2193 (2 > 1 < 9 ..), observe that 2xx will always be greater than 1xx, **so there is no point in keeping the 2**. We should remove the peak and keep the 193.\n        \nWe can also observe the repeated nature of these removals - that is, after one removal the adjacent digits become eligible for removal again. So a stack should be useful here to perform these repeated removals via popping.\n\n# Approach\nWith the above observations, we can have an approach based on using a stack containing the digits. At each step, we iterate through each digit in the input number and make the following decisions:\n\n1. **Identify and remove peaks**: This is based on the prior observation that if we have a peak like 2193, observe that 2xx will always be greater than 1xx, so we should remove the peak.\n\n2. **Add current digit to the stack**: After the repeated removal process (if any), we add the current digit to the stack, as we build our solution iteratively.\n\n3. **Remove remaining digits if k is still positive**: After iterating through all digits, if we still have some removals left (k > 0), we remove the digits from the end of the stack. The string would be something that has no peaks like 12445, just remove as many elements from the right as possible.\n\n**Here is a dry run  of the approach with the sample example given.**\nConsider the sample input num = "2193" and k = 2:\n\n**Initialization**: Stack: []\n**Iteration 1**: Current digit is \'2\'. Stack is empty, so just add \'2\' to the stack. Stack: [\'2\']\n**Iteration 2**: Current digit is \'1\'. \'1\' is smaller than the top of the stack (\'2\'), so **remove the peak**. Pop \'2\' and add \'1\'. Stack: [\'1\']\n**Iteration 3**: Current digit is \'9\'. \'9\' is greater than the top of the stack (\'1\'), so just add \'9\'. Stack: [\'1\', \'9\']\n**Iteration 4**: Current digit is \'3\'. \'3\' is smaller than the top of the stack (\'9\'), so so **remove the peak**. Pop \'9\' and add \'3\'. Stack: [\'1\', \'3\']\n\nk is now 0, no more removals needed.\nHence, the output for the input num = "2193" and k = 2 is "13".\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution:\n    def removeKdigits(self, num: str, k: int) -> str:\n        if not num:\n            return ""\n            \n        stack = []\n        stack.append(num[0])\n        \n        for i in range(1, len(num)):\n            digit = num[i]\n            \n            while stack and stack[-1] > digit and k:\n                stack.pop() # remove peak\n                k -= 1\n            \n            stack.append(digit)\n        \n        while k:\n            stack.pop() # now we just want to remove any additional elements from the end\n            k -= 1\n        \n        res = "".join(stack).lstrip("0")\n        \n        return res if res != "" else "0"\n```\n\nIf this solution helped you understand the problem better, please leave an upvote :)
['Math', 'Stack', 'Greedy', 'Python3']