O(nlogn) and O(n) algo
O(n*log(n)) Using Priority Queue\nO(n) bucket sort\n\n# Code\n\n# Approach : Builtin Priorith Queue:\n\n\n/**\n * O(n*log(n))\n * Runtime: 1 ms, faster than 97.
$$O(n*log(n))$$ Using Priority Queue\n$$O(n)$$ bucket sort\n\n# Code\n\n# Approach : Builtin Priorith Queue:\n```\n\n/**\n * O(n*log(n))\n * Runtime: 1 ms, faster than 97.26% of Java online submissions for Last Stone Weight.\n * Memory Usage: 34.1 MB, less than 100.00% of Java online submissions for Last Stone Weight.\n */\nclass LastStoneWeightPriorityQueue {\n\n    public int lastStoneWeight(int[] stones) {\n        if (null == stones || stones.length == 0)\n            return 0;\n\n        System.out.println(Printer.toString(stones));\n\n        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());\n\n        for (int i = 0; i < stones.length; i++)\n            pq.offer(stones[i]);\n\n        while (pq.size() >= 2) {\n\n            int s1 = pq.poll();\n            int s2 = pq.poll();\n\n            if (s1 != s2)\n                pq.offer(s1 - s2);\n\n        }\n\n        /*\n        for (int i = 0; i < stones.length - 1; ++i)\n            pq.offer(pq.poll() - pq.poll());\n        return pq.poll();\n         */\n\n        return pq.isEmpty() ? 0 : pq.poll();\n    }\n}\n```\n\n# Approach Self made Heap (100% beat)\n\n# code\n```\n  public int lastStoneWeight(int[] stones) {\n            if (stones == null || stones.length == 0)\n                return 0;\n\n            if (stones.length == 1)\n                return stones[0];\n\n            MaxHeap pq = new MaxHeap(stones);\n\n            while (pq.size() >= 2) {\n\n                int x = pq.poll();\n                int y = pq.isEmpty() ? 0 : pq.poll();\n\n                if (x != y) {\n                    // x is the first element, hence always greater or equal to the next element\n                    pq.offer(x - y);\n                }\n\n            }\n\n            return pq.isEmpty() ? 0 : pq.poll();\n\n\n        }\n\n\npublic class MaxHeap {\n\n    int[] heap;\n    int size;\n\n    public MaxHeap(int[] elements) {\n        heap = elements;\n        size = heap.length;\n\n        buildHeap((size - 1) / 2); //last element parent\n    }\n\n    private void buildHeap(int index) {\n        for (int i = index; i >= 0; i--)\n            heapify(i);\n    }\n\n    private void heapify(int index) {\n        if (index < 0 || index >= size)\n            return;\n\n\n        int left = 2 * index + 1;\n        int right = 2 * index + 2;\n        int largest = index;\n\n        if (left < size && heap[left] > heap[largest])\n            largest = left;\n\n        if (right < size && heap[right] > heap[largest])\n            largest = right;\n\n        if (largest != index) {\n            //swap\n            int temp = heap[index];\n            heap[index] = heap[largest];\n            heap[largest] = temp;\n\n            heapify(largest);\n        }\n\n    }\n\n    public int peek() {\n        if (heap != null && size > 0)\n            return heap[0];\n        return Integer.MIN_VALUE;\n    }\n\n    public int poll() {\n\n        if (heap != null && size > 0) {\n            int max = heap[0];\n            heap[0] = heap[size - 1];\n\n            heapify(0);\n            size--;//decrease heap size\n            return max;\n        }\n        return Integer.MIN_VALUE;\n    }\n\n    public void offer(int element) {\n\n        if (heap != null && size >= 0) {\n            size++; //increase heap size\n            int i = size - 1;\n\n            //find its position to be placed\n            while (i > 0 && element > heap[(i - 1) / 2]) {\n                heap[i] = heap[(i - 1) / 2];\n                i = (i - 1) / 2;\n\n            }\n            heap[i] = element;\n\n        }\n\n    }\n\n    public int size() {\n        return size;\n    }\n\n    public boolean isEmpty() {\n        return size == 0;\n    }\n}\n```\n\n# Approach Bucket Sort: $$O(n)$$\nWe can apply bucket sort to achieve linear time complexity.\n\n    Given:\n\n    1 <= stones.length <= 30\n    1 <= stones[i] <= 1000\n    Algorithm:\n\n    1. Find the maximum value in the stones array.\n    2. Create an array of buckets with size equal to the maximum value.\n    3. Count the frequency of each stone in the corresponding bucket.\n    4. Iterate backward through the buckets from the maximum value to 0:\n        a. If a bucket has an even frequency, the stones will destroy each other; move to the next bucket.\n        b. If a bucket has an odd frequency, find another bucket to pair with and update the frequency of the resulting bucket. Decrease the frequency of both buckets as the stones are used.\n    5. Continue this process. At the end, the bucket with a frequency greater than 0 and odd is the result.\n\n    Complexity:\n\n    Space: (O(max)); since 1 <= stones[i] <= 1000, (O(1000)) is constant, thus (O(1)).\n    Time: (O(n)) for counting bucket frequencies + (O(1000)) for iterating through the maximum value of stones. Given the maximum length of stones is 30,\n    in the worst case (all stones are duplicates or unique), the loop runs at most 1000 times, which is constant.\n    Therefore, the overall complexity is:\n\n    Space: (O(1))\n    Time: (O(n + 1000) => approx O(n))\n\n\n# Code\n```\n  public int lastStoneWeight(int[] stones) {\n\n            if (stones == null || stones.length == 0)\n                return 0;\n\n            if (stones.length == 1)\n                return stones[0];\n\n            int max = 0;\n            for (int stone : stones) max = Math.max(max, stone);\n            final int[] buckets = new int[max + 1];\n\n\n            for (int stone : stones) buckets[stone]++;\n\n\n            int i = max, lastJ = max;\n\n            while (i > 0) {\n\n                //skip invalid buckets, for the first run it will be the valid buckets\n                if (buckets[i] == 0) {\n                    i--;\n                } else {\n\n                    //if current max element has even frequency, then they will be pop up together and destroy each other\n                    if (buckets[i] % 2 == 0) {\n                        buckets[i] = 0; //destroy\n                        i--;\n                    } else {\n                        //means the max element and the next max element diff.\n                        int j = Math.min(i - 1, lastJ);\n                        while (j > 0 && buckets[j] == 0) {\n                            j--;\n                        }\n\n                        if (j == 0) {\n                            // no more element left to fight against i, hence i is the answer\n                            return i;\n                        } else {\n\n                            //they will fight each other and destroy each other\n                            buckets[i]--;\n                            buckets[j]--;\n\n                            //if they have different weight, which should be in this case, then we need to update i-j frequency by 1\n                            buckets[i - j]++;\n                            lastJ = j; //cache it\n\n                            //reset i to maximum value in buckets\n                            //max value could be at i-j (due to above diff update, assume i=1000, j=1 => i-j = 999\n                            // max value could be at j, because it was the second last max element in the buckets.\n                            i = Math.max(i - j, j);\n\n                        }\n                    }\n\n\n                }\n\n\n            }\n\n            return 0;\n\n\n        }\n\n```\n\nworst case like \n[1,1,1,1,1,1000] in this case the while(i>0) will run 1000^2 times if we don\'t cache lastJ otherwise 1000 times and if (j==0) then i will be surely that last element where >0 frequency is there \n
['Heap (Priority Queue)', 'Bucket Sort', 'Java']