🔥 [LeetCode The Hard Way] 🔥 Explained Line By Line
We can see that after two stones break we need to replace them back in the array. Where depends on how much they broke down, and it isn\'t always guaranteed to 
We can see that after two stones break we need to replace them back in the array. Where depends on how much they broke down, and it isn\'t always guaranteed to be the end. This points toward a data structure that allows us to restructure efficiently, and that would be a Max Heap.\n\nA max heap is a tree structure that keeps the largest value on top, and for each child the same holds true. When we pop from a heap, the heap will restructure itself to maintain the same dynamics. So 2 pops from a max heap will result in us receiving the 2 largest stones. Pushing back on the heap will place the stones in their correct spot.\n\nNote: A lot of built-in heaps are min heap implementations, to utilize them, we must push the negative weights of the stones on the heap to maintain a max heap structure.\n\nTime Complexity: $$O(nlogn)$$. Where $$n$$ is the size of the heap/stones array. It will take $$n*log(n)$$ time to create the initial heap, then up to $$log(n)$$ time to place the broken-down stones back into the heap.\n\nSpace Complexity: $$O(n)$$. Where $$n$$ is the size of the stones array, to maintain our heap data structure with up to $$n$$ stones inside.\n\n\n```py\n# written by ColeB2\nclass Solution:\n    def lastStoneWeight(self, stones: List[int]) -> int:\n        # initialize an empty array to hold our heap, python uses\n        # arrays, and the heapq module to handle min Heaps. We will\n        # use negative values of the stones to convert to a max heap.\n        heap = []\n        # loop through each stone in our stones array\n        for stone in stones:\n            # push the negative value of the stone onto the heap.\n            # heappush takes the heap array, and the value to push\n            # onto the heap. -stone will allow the min heap to act\n            # as a max heap instead.\n            heapq.heappush(heap, -stone)\n        # We need at least 2 stones to smash together, so we loop while\n        # our heap has at least 2 stones inside.\n        while len(heap) >= 2:\n            # pop both stones off, the 1st is the largest stone.\n            stone1 = heapq.heappop(heap)\n            stone2 = heapq.heappop(heap)\n            # if the second stone is bigger, since we are using negative\n            # values, the second being bigger, means they are not\n            # the same size, and the first is larger. This means\n            # the stone won\'t be completely destroyed, so we need\n            # co calculate the difference to add onto the heap.\n            if stone2 > stone1:\n                # Add onto the heap the difference of stones 1 and 2.\n                heapq.heappush(heap, stone1 - stone2)\n        # remembering that we used negative values of the stones, we \n        # must return the absolute value of the remaining stone if it\n        # exists, else 0 as the question asks.\n        return abs(heap[0]) if heap else 0\n```\n\n```cpp\nclass Solution {\npublic:\n    int lastStoneWeight(vector<int>& stones) {\n        // initialize a priority_queue in c++\n        priority_queue<int> pq;\n        // push the positive value of the stone onto the priority_queue\n        for (int x : stones) pq.push(x); \n        // We need at least 2 stones to smash together, so we loop while\n        // our heap has at least 2 stones inside.\n        while (pq.size() >= 2) {\n            // pop both stones off, the 1st is the largest stone.\n            int y = pq.top(); pq.pop();\n            int x = pq.top(); pq.pop();\n            // if the stones are not same, then the stone of weight x is detroyed\n            // and the stone of weight y has new weight y - x.\n            if (x != y) pq.push(y - x);\n        }\n        // if there are no stones left, return 0\n        if (pq.size() == 0) return 0;\n        // return the weight of the last remaining stone\n        return pq.top();\n    }\n};\n```
['Heap (Priority Queue)', 'Python', 'C++']