Ex-Amazon explains a solution with a video, Python, JavaScript, Java and C++
My youtube channel - KeetCode(Ex-Amazon)\nI create 155 videos for leetcode questions as of April 24, 2023. I believe my channel helps you prepare for the coming
# My youtube channel - KeetCode(Ex-Amazon)\nI create 155 videos for leetcode questions as of April 24, 2023. I believe my channel helps you prepare for the coming technical interviews. Please subscribe my channel!\n\n### Please subscribe my channel - KeetCode(Ex-Amazon) from here.\n\n**I created a video for this question. I believe you can understand easily with visualization.** \n\n**My youtube channel - KeetCode(Ex-Amazon)**\nThere is my channel link under picture in LeetCode profile.\nhttps://leetcode.com/niits/\n\n![aaaaaaa.webp](https://assets.leetcode.com/users/images/d6a4c7b9-262c-497c-b943-a950c6ebdb9f_1682305218.8948395.webp)\n\n\n# Intuition\nUse heap to store stones.\n\n# Approach\n- This is Python algorithm. Other languages might be different.\n\n1. Initialize a variable stones as a heap of negative values of the input stones list using list comprehension. This is done to create a min heap where the most negative value (i.e., the largest absolute value) will be at the root of the heap.\n\n2. Convert the stones list into a heap using the heapify function from the heapq module.\n\n3. While the length of stones is greater than 1, perform the following steps in a loop:\n\n    - Pop the two smallest (most negative) values from the heap and store them in variables s1 and s2.\n    - Check if s1 and s2 are not equal. If they are not equal, calculate the difference between s1 and s2 and negate it (to maintain the negative value) before pushing it back to the heap using the heappush function.\n\n4. After the loop, if the stones heap is not empty, return the negation of the root value (the only remaining value in the heap), which represents the last stone weight. Otherwise, return 0 to indicate that all stones have been destroyed.\n\n---\n\n\n**If you don\'t understand the algorithm, let\'s check my video solution.\nThere is my channel link under picture in LeetCode profile.**\nhttps://leetcode.com/niits/\n\n\n---\n\n# Complexity\n- Time complexity: O(n log n)\nn is the number of elements in the input stones list. This is because the heapify function has a time complexity of O(n) and the while loop iterates n/2 times at most (since two elements are popped from the heap in each iteration), and each iteration involves push and pop operations on the heap which take O(log n) time. Therefore, the overall time complexity is dominated by the heapify function, resulting in O(n log n) time complexity.\n\n- Space complexity: O(n)\nThe stones list is modified in place by converting it into a heap using heapify. No additional data structures are used, and the variables used in the code have constant space requirements. Therefore, the space complexity is proportional to the size of the input stones list, i.e., O(n).\n\n# Python\n```\nclass Solution:\n    def lastStoneWeight(self, stones: List[int]) -> int:\n        if len(stones) == 1:\n            return stones[0]\n        \n        stones = [-s for s in stones]\n        heapq.heapify(stones)\n\n        while len(stones) > 1:\n            s1 = -(heapq.heappop(stones))\n            s2 = -(heapq.heappop(stones))\n\n            if s1 != s2:\n                heapq.heappush(stones, -(s1-s2))\n        \n        return -(stones[0]) if stones else 0\n```\n# JavaScript\n```\n/**\n * @param {number[]} stones\n * @return {number}\n */\nvar lastStoneWeight = function(stones) {\n    const queue = new MaxPriorityQueue();\n    \n    for (stone of stones) queue.enqueue(stone)\n    \n    while (queue.size() > 1) {\n        let first = queue.dequeue().element;\n        let second = queue.dequeue().element;\n        if (first !== second) queue.enqueue(first-second)\n    }\n    \n    return queue.size() === 0 ? 0 : queue.front().element   \n};\n```\n# Java\n```\nclass Solution {\n    public int lastStoneWeight(int[] stones) {\n        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());\n        \n        for (int stone : stones) {\n            queue.offer(stone);\n        }\n        \n        while (queue.size() > 1) {\n            int first = queue.poll();\n            int second = queue.poll();\n            \n            if (first != second) {\n                queue.offer(first - second);\n            }\n        }\n        \n        return queue.size() == 0 ? 0 : queue.peek();\n    }\n}\n```\n# C++\n```\nclass Solution {\npublic:\n    int lastStoneWeight(vector<int>& stones) {\n        priority_queue<int, vector<int>> queue;\n        int s1, s2;\n        \n        for(auto s1:stones)\n            queue.push(s1);\n        \n        while(queue.size() != 1){\n            s2 = queue.top();\n            queue.pop();\n            s1 = queue.top();\n            queue.pop();\n\n            queue.push(s2-s1);\n        }\n        \n        return queue.top();\n    }\n};\n```
['C++', 'Java', 'Python3', 'JavaScript']