EASIEST O(n) explanation and code walk-through
Code is here, explanation is below (recommended to read explanation first)\n\npython\n    def removeKdigits(self, num: str, k: int) -> str:\n        if k == len
Code is here, explanation is below (recommended to read explanation first)\n\n```python\n    def removeKdigits(self, num: str, k: int) -> str:\n        if k == len(num):\n            return "0"\n        \n        out = []\n        for i in range(len(num)):\n            while k and out and out[-1] > num[i]:\n                out.pop()\n                k -= 1\n            out.append(num[i])\n            \n        while k:\n            out.pop()\n            k -= 1\n            \n        return str(int(\'\'.join(out)))\n```\n\nFirst, we have to understand the problem and take a look at the test cases. When we look at the sample test cases and their answers, what pattern do we notice? \n\n`1432219` -> `1219`, deleting `4,3,2`\n\nWe notice that we *delete a number when the next number is smaller*. For example, we delete `4` because of the pair `4,3`, `3` because of `3,2`, and `2` because of `2,1`. We can call pairs such as `4,3` *decreasing pairs*. Thus, we want to create an output array that *always deletes the larger number of at most k decreasing pairs*. \n\nTo implement, we can do that through this code:\n\n```python\n        out = []\n        for i in range(len(num)):\n            while k and out and out[-1] > num[i]:\n                out.pop()\n                k -= 1\n            out.append(num[i])\n```\n\nWe create an array that holds our current output. Every iteration through `num`, we add the element. However, in order to delete the larger number of each decreasing pair, we need a while loop to continuously check that the last element we added isn\'t larger than our current number. Why do we need the while loop instead of just a simple `if nums[i] > nums[i+1]` check? Well consider the following example:\n\n`[0,2,3,4,1]`\n\nIf we want to remove all decreasing pairs, using only  `if nums[i] > nums[i+1]` to delete numbers will result in `[0,2,3,1]` (only the last pair detected). However, this is incorrect, because `3 > 1`. *We need to account for the fact that after we delete an element, the array structure will change, and we may have another decreasing pair*. So instead, we continuously check our output array to make sure the last element we put in also fulfills this condition with the current element in our for loop:\n\n```\nnum[i]=0:    out = [0]                # add 1 because out is initially empty\nnum[i]=2:    out = [0,2]              # add 2, because 0<2\nnum[i]=3:    out = [0,2,3]            # etc.\nnum[i]=4:    out = [0,2,3,4]\nnum[i]=1:    out = [0,2,3,4]          # UH OH, 1<4! time to pop out 4\n             out = [0,2,3]     # UH OH, 1<3! pop out 3\n\t\t\t out = [0,2]       # etc.\n\t\t\t out = [0]         # finally, 1 > 0, so don\'t pop out 0\n\t\t\t out = [0,1]       # add 1\n```\n\nThis is the *key algorithm*, so study it carefully. If you want more practice, check out Merge Intervals (for comparing last element of output array technique) and Sliding Window Maximum (for checking decreasing/increasing pairs technique). Notice that `out` is always increasing (i.e. sorted) for the first `k` decreasing pairs, since we have "corrected" every decreasing pair to be increasing. This is called a monotonic stack/queue, and is a very important concept.\n\nIf we still have some `k` left after going through the entire array, just remove the last element until `k` is zero. We want to remove the biggest elements, and those are at the end of the output array:\n\n```python\n        while k:\n            out.pop()\n```\n\nFor example, take `[1,2,3], k=1`. `[1,2,3]` is already sorted, so there are no decreasing pairs. To find the smallest possible number, it should be obvious that we must remove the largest number of the array (try removing `1` or `2` from the array!). Since the last element is *guaranteed to be the maximum* (remember, the output array is sorted by this point!), we pop `3`. If we have `k=2`, then we need to remove `2` as well, by the same logic.\n\nFinally, convert output array to a string with no leading zeroes. We can do that by converting array->string->int->string. Another solution is `lstrip` for Python, but honestly converting to int to remove leading zeroes works fine too:\n\n```python\nreturn str(int(\'\'.join(out)))\n```\n\nHope this helped!\n
[]