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

algorithm, java, optimization, search

Solution

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.

Problem

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; } ```

Original source