Bucket Sort O(n) beats 99%


  • 0
    J

    Exploiting the fact that "All the integers in the array will be in the range of [-10000, 10000]", perform a bucketization and add every other number to get the maximized sum.

        public int arrayPairSum(int[] nums) {
            int[] buckets = new int[20001];
            for (int x = 0; x < nums.length; x++) {
                buckets[nums[x] + 10000]++;
            }
            boolean odd = true;
            int sum = 0;
            for (int x = 0; x < buckets.length; x++) {
                int freq = buckets[x];
                while (freq != 0) {
                    sum += odd ? (x - 10000) : 0;
                    freq--;
                    odd = !odd;
                }
            }
            return sum;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.