[Python] Beginner-friendly Optimisation Process with Explanation
Introduction\n\nGiven an array of stones stones, we repeatedly "smash" (i.e., compare) the two heaviest stones together until there is at most one stone left. I
### Introduction\n\nGiven an array of stones `stones`, we repeatedly "smash" (i.e., compare) the two heaviest stones together until there is at most one stone left. If the two heaviest stones are of the same weight, both stones are "destroyed" (i.e., both weights become 0), otherwise, a stone with the absolute weight difference of both stones will remain.\n\nNote that the order in which the stones are "smashed" needs to be followed strictly. Otherwise, we will not end up with the correct weight of the remaining stone, if any.\n\n```text\narr = [2, 7, 4, 1, 8, 1]\n\nCORRECT METHOD\n1) Smash 8 and 7 -> arr = [2, 4, 1, 1, 1]\n2) Smash 4 and 2 -> arr = [2, 1, 1, 1]\n3) Smash 2 and 1 -> arr = [1, 1, 1]\n4) Smash 1 and 1 -> arr = [1]\n\nWRONG METHOD #1 (according to index ordering)\n1) Smash 2 and 7 -> arr = [5, 4, 1, 8, 1]\n2) Smash 5 and 4 -> arr = [1, 1, 8, 1]\n3) Smash 1 and 1 -> arr = [8, 1]\n4) Smash 8 and 1 -> arr = [7]\n\nWRONG METHOD #2 (in ascending order)\n1) Smash 1 and 1 -> arr = [2, 7, 4, 8]\n2) Smash 2 and 4 -> arr = [2, 7, 8]\n3) Smash 2 and 7 -> arr = [5, 8]\n4) Smash 5 and 8 -> arr = [3]\n```\n\n---\n\n### Base Approach - Sort and Insert\n\nSince we are required to "smash" the two heaviest stones, we need to know which two stones are the heaviest, and for all iterations. As such, we will first have to sort the stones in order by weight in order to compare the two heaviest stones.\n\n```python\nclass Solution:\n    def lastStoneWeight(self, stones: List[int]) -> int:\n        stones.sort()\n        while stones:\n            s1 = stones.pop()  # the heaviest stone\n            if not stones:  # s1 is the remaining stone\n                return s1\n            s2 = stones.pop()  # the second-heaviest stone; s2 <= s1\n            if s1 > s2:\n                # we need to insert the remaining stone (s1-s2) into the list\n                pass\n            # else s1 == s2; both stones are destroyed\n        return 0  # if no more stones remain\n```\n\nAll that remains now is how we can insert the stone from the "smashing" of the two heaviest stones back into `stones`. The simplest method is to loop through `stones` and insert the stone in the correct index.\n\n```python\nclass Solution:\n    def lastStoneWeight(self, stones: List[int]) -> int:\n        stones.sort()\n        while stones:\n            s1 = stones.pop()  # the heaviest stone\n            if not stones:  # s1 is the remaining stone\n                return s1\n            s2 = stones.pop()  # the second-heaviest stone; s2 <= s1\n            if s1 > s2:\n                # the remaining stone will be s1-s2\n                # loop through stones to find the index to insert the stone\n                for i in range(len(stones)+1):\n                    if i == len(stones) or stones[i] >= s1-s2:\n                        stones.insert(i, s1-s2)\n                        break\n            # else s1 == s2; both stones are destroyed\n        return 0  # if no more stones remain\n```\n\n**TC: O(n<sup>2</sup>)**, where `n` is the length of `stones`, due to the nested inserts.\n**SC: O(1)**, no additonal data structures are used.\n\n---\n\n### Slight Optimisation - Binary Search Insert\n\nAn "optimisation" from the above method to find the index to insert the remaining stone is to binary search for the index to insert to instead of looping through `stones` manually. This involves Python\'s [bisect library](https://docs.python.org/3/library/bisect.html) which has a pre-written function to help us do just that.\n\nNote that we only need to change one portion of the code; the remaining code logic is the same.\n\n```python\nclass Solution:\n    def lastStoneWeight(self, stones: List[int]) -> int:\n        stones.sort()\n        while stones:\n            s1 = stones.pop()  # the heaviest stone\n            if not stones:  # s1 is the remaining stone\n                return s1\n            s2 = stones.pop()  # the second-heaviest stone; s2 <= s1\n            if s1 > s2:\n                # the remaining stone will be s1-s2\n                # binary-insert the remaining stone into stones\n                insort_left(stones, s1-s2)\n            # else s1 == s2; both stones are destroyed\n        return 0  # if no more stones remain\n```\n\n**TC: O(n<sup>2</sup>)**. Even though binary searching for the index to insert to takes O(logn) time, the insert function alone takes O(n) time because it needs to shift all the elements after the index to the right by 1. As such, the overall time complexity for `insort_left()` is O(n).\n**SC: O(1)**, as discussed above.\n\n---\n\n### Data Structure - Heap Implementation\n\nUnfortunately, due to the implementation of the list data structure, even the binary search optimisation cannot break free of the O(n) insert. If only there was a data structure that could help us sort and insert automatically without having to rely on a heavier insert function...\n\nPython has an in-built [heap library](https://docs.python.org/3/library/heapq.html) that is perfect for this task. Essentially, all we need to do is insert the elements, and the heap will settle the sorting order for us. Unfortunately, Python\'s heap library implements a min-heap instead of a max-heap, whereby popping will give us the lightest stone instead of the heaviest stone.\n\nA standard (very common!) workaround is to **negate all the weight values of the stones**. This way, the heaviest stone has the most negative value, and hence becomes the smallest value in the heap. Then, all we have to do after obtaining the value from the heap is to un-negate the value to use it in our calculations.\n\n```python\nclass Solution:\n    def lastStoneWeight(self, stones: List[int]) -> int:\n        # first, negate all weight values in-place\n        for i, s in enumerate(stones):\n            stones[i] = -s\n        heapify(stones)  # pass all negated values into the min-heap\n        while stones:\n            s1 = -heappop(stones)  # the heaviest stone\n            if not stones:  # s1 is the remaining stone\n                return s1\n            s2 = -heappop(stones)  # the second-heaviest stone; s2 <= s1\n            if s1 > s2:\n                heappush(stones, s2-s1)  # push the NEGATED value of s1-s2; i.e., s2-s1\n            # else s1 == s2; both stones are destroyed\n        return 0  # if no more stones remain\n```\n\n**TC: O(nlogn)**; `heappush()` and `heappop()` both have O(logn) time complexity, and are both nested in the while loop. Note: `heapify()` runs in O(n) time, hence the time complexity is not affected.\n**SC: O(1)**; both the negation and the heapify are done in-place.\n\n---\n\nPlease upvote if this has helped you! Appreciate any comments as well :)
['Heap (Priority Queue)', 'Python', 'Python3']