✅ Java | Easy Solution Explained 📝 | Similar Questions | Beginner friendly
Intuition\nSince we need to choose heaviest two stones everytime, this is a clear hint to go for heap data structure. In java we implement heap via priority que
# Intuition\nSince we need to choose heaviest two stones everytime, this is a clear hint to go for heap data structure. In java we implement heap via priority queue.\n\nSimilar questions for heap i faced in interviews.\nLC 347[ Top K Frequent Elements](https://leetcode.com/problems/top-k-frequent-elements/)\nLC 215[ Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array/)\nLC 23 [Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/)\n\n\n---\n# Approach\n1) Make a heap via priority queue, we need to make a max heap as we need heaviest stone collision first.\n2) Add stones[] to heap\n3) Now run a while loop till there are two elements remaining in the hea[] i.e ```while(heap.size()>1)``` Two elements because each collision needs two stones atleast. \n- pick top 2 stones and calculate their difference\n- if difference!=0 we need back to heap other both stones are destroyed.\n4) Once outside the loop, check for size!=0 i.e once stone remains return that or return zero.\n\n---\n# Complexity\n- Time complexity:\nO(nlogn) : Building of heap intially nlogn, Then since we poll and push again to the heap, it needs to rebuild which takes logn(heapify) everytime.\n\n- Space complexity:\nO(n) at max we will have n elements in heap.\n\n---\n\nHope it is easy to understand.\nLet me know if there is something unclear and i can fix it.\n\nOtherwise, please upvote if you like the solution, it would be encouraging\n\n\n---\n# Code\n```\nclass Solution {\n    public int lastStoneWeight(int[] stones) {\n        //setting decreasing order of the heap or max heap\n        PriorityQueue<Integer> heap = new PriorityQueue<>((a,b) -> b-a);\n        for(int each: stones)\n            heap.add(each);\n\n        while(heap.size()>1){\n            int top1 = heap.poll();\n            int top2 = heap.poll();\n            int diff = Math.abs(top1-top2);\n\n            if(diff!=0){\n                heap.add(diff);\n            }\n        }\n\n        if(heap.size()!=0){\n            return heap.poll();\n        }else{\n            return 0;\n        }\n    }\n}\n```
['Heap (Priority Queue)', 'Java']