C++ CountSort / BucketSort solution
Since range of the elements is limited to integers between 1 and 1000, we can easily extend a bucket sort / count sort technique to this problem.\n\n1. Keep cou
Since range of the elements is limited to integers between 1 and 1000, we can easily extend a bucket sort / count sort technique to this problem.\n\n1. Keep count of elements (in say array `arr`) against the indexes derived from their values. So, if we see a value `x`, we increment `arr[x]`. Thus each index is marking the bucket of the index value.\n2. Start from the highest index 1000 and gradually come down to the lowest index 1, smashing rocks along the way. I use two pointers `lo` and `hi` to point to the two rocks that will be smashed in the current iteration. If there are multiple occurrences of a rock, `lo` and `hi` might point to the same index / bucket.\n\n```\nclass Solution {\npublic:\n    int lastStoneWeight(vector<int>& stones) {\n        int arr[1010] = {0};\n        \n        for(auto num: stones)\n            arr[num]++;\n        \n        int hi = 1000, lo = hi;\n        while(lo > 0 && hi > 0) {\n            while(hi > 0 && arr[hi] < 1)\n                hi--;\n            \n            if(hi < 1)\n                break;\n            \n            lo = arr[hi] > 1 ? hi : hi-1;\n            while(lo > 0 && arr[lo] < 1)\n                    lo--;\n            \n            if(lo < 1)\n                break;\n            \n            // smash!\n            arr[hi-lo]++;\n            arr[hi]--;\n            arr[lo]--;\n        }\n        \n        return hi * (arr[hi] > 0);\n    }\n};\n```\n\n+ Uses extra linear space in the order of the range of elements.\n+ Runs in linear time in the order of the number of elements.
[]