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

Duplicate: Here's the best approach http://stackoverflow.com/questions/4720271/find-a-pair-of-elements-from-an-array-whose-sum-equals-a-given-number?rq=1 — Pepe, Nov 24 '13 at 06:36

Vikram Bhat · Answer 1 · 2013-11-24T08:04:54.343

7

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.

edited Nov 24 '13 at 08:04

answered Nov 24 '13 at 07:16

Vikram Bhat

5,972
3
18
19

This is a good approach. You should also mention that it is a better approach if memory is not an issue since it necessarily would require O (n) extra space whereas the other solutions can be implemented in-place. – Abhishek Bansal Nov 24 '13 at 07:35
@Abhishek U are right i always make space complexity analysis but missed this time. Check my Edit. – Vikram Bhat Nov 24 '13 at 08:03
There is no add() in HashMap – Vivin Aug 21 '16 at 02:06
@Kode Yes that is why I have specified it is a pseudo code. – Vikram Bhat Aug 22 '16 at 09:02
1

hi, k can be 0. your solution won't work on this case – nathan Mar 05 '17 at 03:37

Abhishek Bansal · Answer 2 · 2013-11-24T09:02:33.403

0

In your 1st code, your inner loop termination condition is incorrect. It should terminate if the beg and end pointers cross each other.

Change it to while (beg <= end) or for (; beg <= end; )

Also, for the second approach there is no need for sorting the array.

edited Nov 24 '13 at 09:02

answered Nov 24 '13 at 06:47

Abhishek Bansal

12,447
4
29
44

In the second case, although sorting doesn't actually help in reducing the order of the algorithm, yet it might help to reduce a significant overhead in the linear scan if the value of k is small. Of course worst case, both perform the same. – sushant-hiray Nov 24 '13 at 07:22
@Sushant by your logic what would happen if difference is large? – Abhishek Bansal Nov 24 '13 at 07:32
@AbhishekBansal : In case i dont use the sorting for the approach 2 .Then i need to search for temp-a[j]==-k and temp-a[j]==k , so for this more or less the time complexity will be O(n^2). While if i sort the array first the running time for multiple test cases are less. – Sahil Gupta Nov 24 '13 at 08:00
@user3026672 if you are conducting a linear search then the time complexity for each test case shall be O (n^2) whether or not the array is sorted. – Abhishek Bansal Nov 24 '13 at 08:11
@AbhishekBansal : Thanks abhishek for the replies :) – Sahil Gupta Nov 24 '13 at 13:12
@AbhishekBansal : Thanks :) – Sahil Gupta Nov 24 '13 at 13:15

score 0 · Answer 3 · answered Jul 16 '16 at 20:07

You can also use set no need to use hashmap

public static void main(String[] args) throws Exception {

    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    int[] firstLine = Stream.of(in.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    int count = firstLine[0];
    int diff = firstLine[1];           
    Set<Integer> numbers = new HashSet<Integer>(Stream.of(in.readLine().split(" ")).map(Integer::valueOf).collect(Collectors.toList()));

    int pairCount = 0;
    for (Integer number : numbers) {
        pairCount += (numbers.contains(number+diff) ? 1:0); 
    }
    System.out.println(pairCount);                
}

score 0 · Answer 4 · answered Oct 27 '16 at 00:19

private static int CountDistinctPairs(int[] nums, int k) {
    // TODO Auto-generated method stub
    HashMap<Integer, Boolean> map = new HashMap<Integer, Boolean>();
    HashSet<String> set = new HashSet<String>();
    for(int i =0;i < nums.length;i++){
        map.put(nums[i],true);
    }
    for (int i = 0 ; i < nums.length; i++){
        if(map.containsKey(nums[i]+k)){
            String a = "";
            if(nums[i]<nums[i]+k){
                a = "("+nums[i]+","+(nums[i]+k)+")";
            }
            else{
                a = "("+(nums[i] + k)+","+nums[i]+")";
            }
            set.add(a);
        }
    }
    System.out.println(set);
    return set.size();
}

score 0 · Answer 5 · answered Oct 13 '17 at 05:44

My solution

System.out.println("findPair:"+findPair(new int[]{4,7,1,2,5,3,0,7,8,5,2}, 3));

public static int findPair(int[] nums, int target){ 
    Arrays.sort(nums);

    int count = 0;
    String pairText = "";
    for(int i =0; i < nums.length;i++){
        for(int j =i+1; j < nums.length;j++){

            if(nums[j]-nums[i] == target && (!pairText.equals(nums[i]+", "+nums[j]))){

                //System.out.println(nums[i]+", "+nums[j]);
                pairText = nums[i]+", "+nums[j];
                count++;
            }
        }

    }  


    return count;


}

score -1 · Answer 6 · answered Jun 22 '17 at 11:45

static boolean checkDuplicatesWithinK(int arr[], int k)
    {
        // Creates an empty hashset
        HashSet<Integer> set = new HashSet<>();

        // Traverse the input array
        for (int i=0; i<arr.length; i++)
        {
            // If already present n hash, then we found 
            // a duplicate within k distance
            if (set.contains(arr[i]))
               return true;

            // Add this item to hashset
            set.add(arr[i]);

            // Remove the k+1 distant item
            if (i >= k)
              set.remove(arr[i-k]);
        }
        return false;
    }

public static void main (String[] args)
    {
        int arr[] = {10, 5, 3, 4, 3, 5, 6};
        if (checkDuplicatesWithinK(arr, 3))
           System.out.println("Yes");
        else
           System.out.println("No");
    }

could you add some explanation to this code? to improve your answer and to help future readers — WhatsThePoint, Jun 22 '17 at 12:15

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

6 Answers6