java public static int pairs(int k, List arr) { int count = 0; int start = 0; Collections.sort(arr); for(int i = 1; i < arr.size(); i++){ int diff = arr.get(i) - arr.get(start); if(diff > k) { start++; i--; } else if (diff == k) { count++; start++; } } return count; }

Java solution using Lambdas

public static int pairs(int k, List<Integer> arr) {
    // Write your code here
    Set<Integer> complementSet = ConcurrentHashMap.newKeySet();
    arr.stream().forEach(f -> complementSet.add(f));
    return (int) arr.parallelStream().filter(d -> complementSet.contains(k + d)).count();
}

}

Golang Time Complexity: O(n) Space Complexity: O(n)

First: populates a hash map with all elements from the input array arr for quick lookups.

Second: For each element x, it checks if x - k and x + k exist in the hash map. if exist, count

The current element x is then removed from the hash map to prevent counting the same pair twice (e.g., counting (3, 5) when x=3 and then again when x=5)

func pairs(k int32, arr []int32) int32 {
exist := make(map[int32]bool)
for _, x := range arr {
    exist[x] = true
}

count := int32(0)
for _, x := range arr {
    if exist[x-k] {
        count++
    }
    if exist[x+k] {
        count++
    }
    exist[x] = false
}
return count

}

`

My Java 8 solution, which passes all test cases, for a Max Score of 50:

(1) Sort the Array in Ascending Order.

(2) Iterate through the array sequentially from arrIndex = 0 all the way to arrIndex = arr.size() - 2, and do the following:

(2) (a) Make a subList which spans from arrIndex + 1 to the last index of the array. This is our way of narrowing our search space. We expect the other value in the pair to occur in this space.

(2) (b) For the element at arr[arrIndex] : do a "Binary Search" through the Narrowed Sorted Sublist (costing O(log (n)) - to attempt to find the "other corresponding expected value", which would result in the "target difference". If search is successful, then Another Pair has been FOUND. At this point, we also increment the subListStartIndex, narrowing our search space further.

Overall Expected Worst Case Time Complexity: O(n * log(n)).

    public static int pairs(int k, List<Integer> arr) {
        // Write your code here
        int numPairs = 0;

        Collections.sort(arr);
        
        for (int arrIdx = 0, subLstStrtIdx = (arrIdx + 1) ; 
             arrIdx < (arr.size() - 1) && subLstStrtIdx <= (arr.size() - 1) ; 
             arrIdx++) {

            int curElemVal = arr.get(arrIdx);
            int otherExpElemVal = (curElemVal + k);
            
            List<Integer> curSubLst = getSubList(arr, subLstStrtIdx, arr.size());

            int otherExpElemIdx = 
                Collections.binarySearch(curSubLst, otherExpElemVal);
                
            if (otherExpElemIdx >= 0) {

                // Other Expected Element found - arrIdx.e. Another Pair Found.
                numPairs++;
                // We can narrow the Search-Space further.
                subLstStrtIdx += (otherExpElemIdx + 1);

            }
        }
        
        return numPairs;
    }