Best way to find the number of pairs in an array whose difference is k

Question

I was solving the problem on hackerrank. I had two approaches in my mind :

input : unsorted array(a) and k

First Approach :

1) Sort the array

2) for each array element a[i] ,find the element a[i]+K using binary search.If found increament the count and break the inner loop.

Second Approach :

1) Sort the array

2) for each array element a[i] ,find the element a[i]+K using linearsearch.If found increament the count and break the inner loop.

I found the First approach to be better as it will solve the problem in n(logn). But when multiple test cases are on the solutions the approach 2 takes lesser time . Can some one please explain why ?

Below are the code for the two approaches :

First Approach Code :

static int pairs(int[] a,int k) {
  /* Complete this function */
    int temp;
    int len=a.length;
    int count=0;
    int beg;
    int mid;
    int end;
    int midVal;
    Arrays.sort(a);
    for(int i=0;i<len-1;i++){
    temp=a[i]+k;
    beg=i+1;  
    end=len-1;
        for(int l=beg;l<len;l++){
            mid=(beg+end)/2;
            midVal=a[mid];
            if(midVal==temp){
                count++;
                break;
            }
            else if(midVal>temp){
                end=mid-1;
            }
            else{
                beg=mid+1;
            }
        }

    }
    return count;
}

Second Approach Code :

static int pairs(int[] a,int k) {
  /* Complete this function */
    int temp;
    int len=a.length;
    int count=0;
    Arrays.sort(a);
    for(int i=0;i<len;i++){
    temp=a[i];
        for(int j=i+1;j<len;j++){
            if(temp-a[j]==-k){
                count++;
                break;
            }
        }
    }
    return count;
}

Answer 1

The first approach is the best here among the two but there is better approach than both:-

Here a pseudo code for a better approach:-

for(i=0;i<Arr.length;i++) {
  Hashmap.add(Arr[i])
}
count=0;
for(j=0;j<Arr.length;j++) {

  if(Hashmap.containsKey(Arr[j]+k))
     count++;

}

Time complexity: O(N) whereas your approach = O(NlogN)

Edit:-

Note:- My approach has extra space complexity of O(N) for Hash table whereas suggested approach is inplace.