✅2 approaches: Sorting & Max Heap with explanations!
If you\u2019re interested in coding you can join my Discord Server, link in the comment section. Also if you find any mistakes please let me know. Thank you!\u2
> **If you\u2019re interested in coding you can join my Discord Server, link in the comment section. Also if you find any mistakes please let me know. Thank you!\u2764\uFE0F**\n> \n\n\n---\n\n## Explanation:\n\n### Solution 01\n\n- ***Brute force solution*** //not recommended.\n- Here every iteration we\u2019re sorting the array & changing the last 2 values.\n- As the last 2 are the max elements, so ***x=stones[n-2]*** & ***y=stones[n-1].***\n- We\u2019ll replace x with 0 (as all elements will be greater than 0), and y with y-x.\n- Return the last element after n iteration.\n- **Time complexity:** O(n^2logn).\n\n### Solution 02\n\n- Using ***Max Heap.***\n- Max heap keeps the maximum element on top.\n- First, we\u2019ll push all the elements of stones to our max heap.\n- Now until the size of our heap won\u2019t became 1 we\u2019ll continue this operation:\n    - Take the top element to y & pop that element. `y = q.top(); q.pop();`\n    - Similarly, put the next element to x & pop it. `x = q.top(); q.pop();`\n    - Now smallest element will destroy & we\u2019ll push y-x to our heap again. In the case of same weight elements, it will automatically push 0. `q.push(y-x);`\n    - When the size of the heap became 1 we\u2019ll break the loop and return top element.\n- **Time complexity:** O(nlogn).\n\n---\n\n## Code:\n\n```cpp\n//Solution 01:\nclass Solution {\npublic:\n    int lastStoneWeight(vector<int>& stones) {\n        int n = stones.size(), ans, count = 0;\n        \n        if(n == 1) return stones[0];\n        \n        while(count != n-1){\n            sort(stones.begin(), stones.end());\n            stones[n-1] = stones[n-1] - stones[n-2];\n            stones[n-2] = 0;\n            count++;\n        }\n        return stones[n-1];\n    }\n};\n\n//Solution 02:\nclass Solution {\npublic:\n    int lastStoneWeight(vector<int>& stones) {\n        priority_queue<int, vector<int>> q;\n        int x, y;\n        \n        for(auto x:stones)\n            q.push(x);\n        \n        while(q.size() != 1){\n            y = q.top();\n            q.pop();\n            x = q.top();\n            q.pop();\n\n            q.push(y-x);\n        }\n        \n        return q.top();\n    }\n};\n```\n\n---\n\n> **Please upvote this solution**\n>
['C', 'Sorting', 'Heap (Priority Queue)', 'C++']