A solid EXPLANATION
How\'s going Ladies - n - Gentlemen, today we are going to solve another coolest problem i.e. Last Stone Weight \n\nOkay, so first of all let\'s understand the 
How\'s going Ladies - n - Gentlemen, today we are going to solve another coolest problem i.e. **Last Stone Weight** \n\nOkay, so first of all let\'s understand the problem\n\n**We have 2 stones x & y**\n\n![image](https://assets.leetcode.com/users/images/e062b588-f311-49ea-9aa0-c19e720eb38a_1649295151.330421.png)\n\nAnd There could be 2 Possiblities :\n* If both the stones x & y have same weight, then **` x == y, both stones are destroyed`**\n\n\n* If they are not equal, then stone y always be greater then stone x, therefore **`x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.`** \n\n```\nAt the end of the game, there is at most one stone left.\n\nReturn the smallest possible weight of the left stone. If there are no stones left, return 0.\n```\n\nI hope problem statement is absolute clear, now let\'s talk about how we gonna solve this problem.\n\n**Let\'s take an example,**\n\n**Input**: stones = [2,7,4,1,8,1]\n**Output**: 1\n\nThe very Brute force Idea came in our mind is, why don;t we just sort that array, such that we will have bigger values in the end, and to maintain that highest value in the end, we always gonna sort them once both of the stones will collide. \n\nWhat I mean is, let\'s take our input array:\n```\n[2,7,4,1,8,1]\n\nLet\'s sort it:\n\n[1,1,2,4,7,8]\n```\n\nNow what we gonna do is, collide the 2 stones and get their difference i.e. `y - x`\n```\n[1,1,2,4,7,8]  -->  y = 8      &      x = 7\n\nThus,\ny - x    -->  8 - 7 = 1\n```\nNow we gonna put that one in our array & maintain the order by sorting it back again\n```\n[1,1,2,4]          add => 1   in our array\n\n[1,1,2,4,1]          now again sort it,\n\n[1,1,1,2,4]\n```\nSo, we gonna perform the same step for all. Well it\'s not a great approach to go with, as our Time Complexity will be much higher.\n\nLet\'s code it up, then we gonna analysis it\'s space & time complexity:-\n\n```\nclass Solution {\n    public int lastStoneWeight(int[] stones) {\n        Arrays.sort(stones);\n        \n        for(int i = stones.length - 1; i > 0; i--){\n            stones[i - 1] = stones[i] - stones[i - 1];\n            Arrays.sort(stones);\n        }\n        return stones[0];\n    }\n}\n```\n\nANALYSIS :-\n* **Time Complexity :-** BigO(NlogN) * BigO(N) => BigO(N^2logN)\n\n* **Space Complexity :-** BigO(1)\n\nWell, now you say. Dude, let;s optimise it. \nYes, we just goona do that stuff now!!\n```\nFor Optimising it, we gonna use the help of Heap\n```\n\nOkay, so we gonna take the same example & now you\'ll ask which heap do we have to use??\n**minHeap OR maxHeap??**\n\nAs, you can see we want highest value at the first & lowest value in the last. So, we gonna use **maxHeap**\n\nLet\'s create our maxHeap and use the same example i.e. **`[2,7,4,1,8,1]`** to fill our heap.\n\nSo, our first job is, let\'s fill our heap.\n```\n                Array           [2,7,4,1,8,1]\n|     |\n|\t  |\t\t\n|     |  \n|     |\n|     |\n|     |\n--------\nmaxHeap\n```\n\nNow let\'s fill our heap,\n```\n                Array           [2,7,4,1,8,1]\n\t\t\t\t                 ^\n|     |\n|\t  |\t\t\n|     |  \n|     |\n|     |\n|  2  |\n--------\nmaxHeap\n```\n```\n                Array           [2,7,4,1,8,1]\n\t\t\t\t                   ^\n|     |\n|\t  |\t\t\n|     |  \n|     |\n|  7  |\n|  2  |\n--------\nmaxHeap\n```\n```\n                Array           [2,7,4,1,8,1]\n\t\t\t\t                     ^\n|     |\n|\t  |\t\t\n|     |  \n|  7  |\n|  4  |\n|  2  |\n--------\nmaxHeap\n```\n```\n                Array           [2,7,4,1,8,1]\n\t\t\t\t                       ^\n|     |\n|\t  |\t\t\n|  7  |  \n|  4  |\n|  2  |\n|  1  |\n--------\nmaxHeap\n```\n```\n                Array           [2,7,4,1,8,1]\n\t\t\t\t                         ^\n|     |\n|  8  |\t\t\n|  7  |  \n|  4  |\n|  2  |\n|  1  |\n--------\nmaxHeap\n```\n```\n                Array           [2,7,4,1,8,1]\n\t\t\t\t                           ^\n|  8  |\n|  7  |\t\t\n|  4  |  \n|  2  |\n|  1  |\n|  1  |\n--------\nmaxHeap\n```\n\nNow it\'s time to get the stone x & y using our heap & after calculating **`y - x`** put the new difference in our stack\n```\n                Array           [2,7,4,1,8,1]\n\t\t\t\t                           \n|     |         y = 8\n|     |\t\t    x = 7\n|  4  |      \n|  2  |         and their result will be y - x => 8 - 7 = 1\n|  1  |\n|  1  |\n--------\nmaxHeap\n```\nNow put that **1** into our heap & again calculate the result of stone x & y\n```\n                Array           [2,7,4,1,8,1]\n\t\t\t\t                           \n|     |         y = 4\n|     |\t\t    x = 2\n|     |      \n|  1  |         and their result will be y - x => 4 - 2 = 2\n|  1  |\n|  1  |\n--------\nmaxHeap\n```\nSo, we gonna perform the same step until & unless only 1 elemnent left in our stack.\n\nI hope so, ladies - n - gentlemen, approach is absolute clear, **then let\'s code it up:**\n\n```\nclass Solution {\n    public int lastStoneWeight(int[] stones) {\n        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());\n        for(int v : stones){\n            maxHeap.offer(v);\n        }\n        int x;\n        int y;\n        while(maxHeap.size() > 1){\n            y = maxHeap.poll();\n            x = maxHeap.poll();\n            if(y > x){\n                maxHeap.offer(y - x);\n            }\n        }\n        if(maxHeap.size() == 0) return 0;\n        return maxHeap.poll();\n    }\n}\n```\nANALYSIS :-\n* **Time Complexity :-** BigO(NlogN)\n\n* **Space Complexity :-** BigO(N)\n```\nTime Complexity Explanation\'s may be still if I\'m wrong, correct me then, THANKS <^^>\n```\n\n*Heap is a specialized tree-based data structure* that is essentially almost *complete binary tree.* There are so many operations possible with **max and min heaps like -**\n\n`insert(), delete(), update(), findMinElement(), findMaxElement(), etc`\n\nAnd time complexity depends on the operation you perform on the heap.\n\n**`Heap Sort has O(nlog n) time complexities for all the cases ( best case, average case, and worst case).`**\n\n**Let us understand the reason why.** The height of a complete binary tree containing n elements is **log n**\n\nIn the worst case scenario, we will need to move an element from the root to the leaf node making a multiple of **log(n)** comparisons and swaps.\n\nDuring the `build_max_heap` stage, we do that for **n/2** elements so the worst case complexity of the `build_heap` step is **n/2xlog n ~ nlog n**.\n\nDuring the sorting step, we exchange the root element with the last element and heapify the root element. For each element, this again takes **log n** worst time because we might have to bring the element all the way from the root to the leaf. Since we repeat this n times, the `heap_sort` step is also **nlog n.**\n\nAlso since the `build_max_heap` and `heap_sort` steps are executed one after another, the algorithmic complexity is not multiplied and it remains in the order of **nlog n**.
[]