[Java] Simple solution based on Counting Sort, Accepted


  • 0
    J

    Since we know that 0 <= nums[i] < 1000000, the max that the distance can be is 999,999. Once distances is populated, just iterated over occurrences of distances until we've reached k

        public int smallestDistancePair(int[] nums, int k) {
            int[] distances = new int[1000000];
            for (int i = 0; i < nums.length - 1; i++) {
                for (int j = i + 1; j < nums.length; j++) {
                    distances[Math.abs(nums[i] - nums[j])]++;
                }
            }
            
            int idx = 0;
            for (int i = 0; i < distances.length; i++) {
                int count = distances[i];
                
                for (int j = 0; j < count; j++) {
                    idx++;
                    if (idx == k) {
                        return i;
                    }
                }
            }
            
            return -1;
        }
    

Log in to reply
 

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