Gotchas | Hints | Breakdown | Implementation (Python)
A Quick Introduction\n\nWhen I get stuck, all I ever really want is a hint. But often I find myself stumbling across the answer to the problem before I\'ve even
# A Quick Introduction\n\nWhen I get stuck, all I ever really want is a hint. But often I find myself stumbling across the answer to the problem before I\'ve even found a decent hint. So I\'m proposing a style of post that will be easily searchable and sticks to a format:\n1. Gotchas\n      - you may have solved the problem, but you\'re wondering if there is a **more optimal way** of solving it.\n      - Gotchas are here to show you if there\'s a better way, and check you\'ve covered your **edge cases**.\n2. Hints\n\t- An well written hint goes a long way\n\t- Generally it should first guide someone to solving the solution using a **brute force** method\n\t- Next, it may present you another test case you didn\'t consider that sheds light on the answer.\n\t- It may also introduce a **data structures** people may not have encountered before.\n\t- *Then* it can introduce hints to more **optimal solutions**.\n3. Breakdown\n\t- This is a solution written **IN PSEUDOCODE**.\n\t- Use **well named variables** and **comments giving reasoning**, short lazy pseudocode just defeats the object.\n\t- Followed by a **complexity analysis**, of both time and space. *No skipping the space complexity just because you find it hard to analyse the space complexity of your Breadth First Search algorithm.*\n4. Implementation\n\t- Use a language of your choice, but follow the guidance of your own pseudocode.\n\t- No "one-liners" that don\'t actually add anything to the speed of the algorithm, this is a teaching tool.\n\nWhen naming your post follow this format:\n**Gotchas | Hints | Breakdown | Implementation (Language_1, Language_2, etc)**\n\nFinally, we all make mistakes. So if you\'re going through the effort, give it a proof read.\n\n# Gotchas\n-  This problem can be solved in O(n) time using O(n) space\n# Hints\n___\n(1) Break the problem down and **solve it by hand**, solving the simplest problem first. We\'ll use the example input `num = 123654`. \n\nStart with k = 1. What digit would you remove? Now increase k to 2, what are the first 2 digits you remove?  In selecting those first 2 digits what digits did you need to consider? Next increase k to 3. See a pattern?\n\nAs you iterate  through the digits from left to right you need to evaluate each number against the previous. You are trying to determine what has more impact on the resulting number number. \n\nWorking through our example case when k = 1 we compare the values 13654, 12654, *12354*, 12364... wait we\'ve found it, 6 was the number we needed to remove. Increasing k to 2, we continue find we can continue from where we were and next remove 5. Next when k = 3 we remove 4 leaving us with *123*.\n\nNow something interesting happens, if we increase k to 4 (then 5), we now need to work backwards through the elements we\'ve already parsed. So when k = 4, the output is *12* and k = 5, the output is *1*.  If the number to the right is smaller than the previous number then the previous number is removed.\n\n___\n(2) Now you may have recognised that there is a data structure that can help us with this problem, *a stack* but more specifically a **monotonic stack**. Simply, a monotonic stack (or queue) is a data structure that keeps a strictly increasing, or decreasing order of numbers. Here\'s a great explanation on [Medium](https://medium.com/algorithms-and-leetcode/monotonic-queue-explained-with-leetcode-problems-7db7c530c1d6).\n\nUsing a monotonic increase stack, we can now keep track of what numbers take priority and remain in the output number. Any number that is removed from the stack must be counted. So, if we keep track of the total number of elements removed from the stack, we can stop removing elements once our count gets to k.\n___\n(3) Once we\'ve reached removed k elements from the stack, we can continue parsing our input (`num`) and add the remaining elements. BUT, now we need to handle all of those **zeros** and they are at the bottom of the stack. Easy, instead of using a stack let\'s use a Queue (or a Doubly Linked List).\n\n\n# Breakdown\nIf you were impatient and just skipped ahead without implementing I get it. Below the pseudocode you\'ll find **Time Complexity** and **Space Complexity** analysis.\n\nPsuedocode:\n```pseudocode\n    function removeKdigits(num, k):\n\n        // First lets handle our edge case, if k is the same size as num we can \n        // immediately return 0.\n        if num.length <= k:\n            return "0"\n\t\t  // It\'s not entirely necessary as it will return the same output but we\n\t\t  // may as well check if k is 0\n\t\t  if k == 0:\n\t\t\t  return num\n        \n        queue = DoublyLinkedList()\n        total_deleted = 0\n        \n\t\t  // in this for loop we implement what would be considered the monotone\n        // increase stack, with the condition that it stops deleting items once\n        // total_deleted reaches.\n\t\t  // NB: We can also compare chars like ints so no need to cast them.\n        for i in 0 -> num.length - 1:\n            while queue.length > 0 && num[i] < queue.tail && total_deleted < k:\n                queue.pop_tail()\n                total_deleted += 1\n            queue.add_tail(num[i])\n        \n\t\t  // if we haven\'t deleted k elements from the queue we can now just\n        while total_deleted < k:\n            queue.pop_tail()\n            deleted += 1\n        \n        // remove all of the leading zeros. If there is only zeros leave one!\n        while queue.peak_head() == \'0\' and len(q) > 1:\n            q.pop_head()\n        \n\t\t  // Add all the remaining chars in the queue together into one string.\n        output = concatenate(queue)\n        return output\n```\n\n# Complexity\nTime complexity:\n- At its worst this algorithm adds  `num.length` (**n**) elements to `queue`, and removes all of them. As these are constant time operations O(1), this makes a total number of operation proportional to n.\n- Plus, concatenating all of the elements remaining in `queue` will take at most n-1 if k=1\n- So roughly O(n + n)  is **O(n)**\n\nSpace complexity:\n- We created a doubly linked list that will store at most all characters in the input array, so its size would be proportional to n.\n- At the end we create a new string by concatenating all the remaining chars in `queue`, with a maximum length of n-1.\n- So roughly O(n + n - 1)  is **O(n)**\n\n\n# Implementation\n\nA python imlemenntation:\n```python\nfrom collections import deque\n\nclass Solution:\n    def removeKdigits(self, num, k):\n        if len(num) <= k:\n            return \'0\'\n\t\t  if k == 0:\n\t\t\t  return num\n        \n        q = deque()\n        deleted = 0\n        \n        for i in range(len(num)):\n            while len(q) > 0 and num[i] < q[-1] and deleted < k:\n                q.pop()\n                deleted += 1\n            q.append(num[i])\n        \n        while deleted < k:\n            q.pop()\n            deleted += 1\n        \n        while q[0] == \'0\' and len(q) > 1:\n            q.popleft()\n        \n        return = \'\'.join(q)\n```
[]