Java simple to complex solutions explained -- 0 ms top 100% time 100% memory 2 lines of code only!
At every step of the algorithm, we need to know the top heaviest stone.\nThe most efficient way to retrieve the max for large input sizes is to use a max heap, 
At every step of the algorithm, we need to know the top heaviest stone.\nThe most efficient way to retrieve the max for large input sizes is to use a max heap, which in Java is a PriorityQueue (min heap) with a reverse comparator:\n\nO(n log (n)) time O(n) space \n1 ms time 37.5 MB space\n91% time 100% space\n\n```\n    public int lastStoneWeight(int[] stones) {\n        PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());\n        for(int i : stones) {\n            queue.add(i);\n        }\n        int x;\n        int y;\n        while(queue.size() > 1) {\n            y = queue.poll();\n            x = queue.poll();\n            if(y > x) {\n                queue.offer(y-x);   \n            }\n        }\n        return queue.isEmpty() ? 0 : queue.poll();\n    }\n```\n\nBut we can do better, right? If you have done a few of these problems you might know to use BucketSort with has constant access and no typical "sorting", we can do O(n) time. \n\nHowever, it is more accurate to say the time would be O(n + maxStoneWeight) because we will build a bucket for every possible weight. And usually a O(n + 1000) would be a great solution, but the test cases here have a very short input size. the number of stones goes only from 0 to 30, so this solution actually performs worse than O(n) since n is at most 30! O(30) == O(1030) but 30 < 1030. Both have the same complexity, but the first runs faster, and you might have not noticed why unless you check the inputs given in the tests.\n\n```\n    int[] buckets = new int[1001];\n    for(int stone: stones)\n      buckets[stone]++;\n    int i = 1000;\n    int j;\n    while(i > 0) {\n      if(buckets[i] == 0) {\n        i--;\n      } else {\n        buckets[i] = buckets[i] % 2;\n        if(buckets[i] != 0) {\n          j = i-1;\n          while(j > 0 && buckets[j] == 0)\n            j--;\n          if(j == 0)\n            return i;\n          buckets[i - j]++;\n          buckets[j]--;\n          i--;\n        }\n      }\n    }\n    return 0;\n```\n\nRuns even slower! Remember to not always apply a solution that seems faster because you didn\'t consider your context or use cases. here the number of stones is much smaller than the weight of the stones.\n\nSo if we know that the number of stones is quite small, can we do even better than the PriorityQueue? What is a very fast sorting algorithm for small sets, better than building a heap? Sort in place in the array! Don\'t waste time building new objects or copies of the input.\n\nO( n^2 log(n) ) because for every stone n, we sort the array O(nlog(n))\nO(1) space, no extra space, sort in place\n**0 ms time 36.9 MB\tspace\nfaster than 100% and less space used than 100% of other solutions**\n\n```\n  public static int lastStoneWeight(int[] stones) {\n    Arrays.sort(stones);\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\nAnd just for fun, let\'s mangle it into **2 lines**:\n```\n    for(int i=stones.length; i>0; stones[i-1] = i==stones.length? stones[i-1] : stones[i] - stones[i-1], Arrays.sort(stones), i--);\n    return stones[0];\n```\n\nEDIT: \nTo be completely clear, if the input size was unrestricted and not less than 30 stones, BucketSort would be the best solution because it runs in O(maxStoneWeight). If the stones weight is not unrestricted, then BucketSort cannot work as you would need 2,147,483,647 buckets. In that case, PriorityQueue would be the best solution.\n\n**In an interview, you should only discuss either BucketSort or PriorityQueue (max head) solutions**. The only reason I mentioned the sorting solution, which is much worse than the two other solutions, is because the input size in the tests of this challenge are so small that this solution is faster.
[]