Break the CODE!!!: Interviewstreet Challenge: Pairs

http://www.geeksforgeeks.org/count-pairs-difference-equal-k/

Given an integer array and a positive integer k, count all distinct pairs with difference equal to k.

Input: arr[] = {1, 5, 3, 4, 2}, k = 3
Output: 2
There are 2 pairs with difference 3, the pairs are {1, 4} and {5, 2} 

Input: arr[] = {8, 12, 16, 4, 0, 20}, k = 4
Output: 5
There are 5 pairs with difference 4, the pairs are {0, 4}, {4, 8}, 
{8, 12}, {12, 16} and {16, 20} 

O(nlogn)
Now apply a modified version of binary search. So take each number 'x' and do a binary search for (x+k). If its found they make a pair. Now take the next number in the sorted array and so on.

X. Pre-sort + two pointers 夹逼法  http://comproguide.blogspot.com/2014/01/finding-number-of-pairs-in-array-with.html

1. Take two indices and point them to first and second elements.
2. Repeat the following steps until any index reaches the end of the array
1. If the difference matches, increment count and increment both the indices
2. If the difference is less than required value,  increment second index
3. Otherwise increment first index.

int countPairsWithDiffK(int arr[], int n, int k)

{

    int count = 0;

    sort(arr, arr+n);  // Sort array elements

 

    int l = 0;

    int r = 0;

    while(r < n)

    {

         if(arr[r] - arr[l] == k)

        {

              count++;

              l++;

              r++;

        }

         else if(arr[r] - arr[l] > k)

              l++;

         else // arr[r] - arr[l] < sum

              r++;

    }  

    return count;

}

X. Pre-sort + Binary Search http://www.geeksforgeeks.org/count-pairs-difference-equal-k/

1) Initialize count as 0
2) Sort all numbers in increasing order.
3) Remove duplicates from array.
4) Do following for each element arr[i]
   a) Binary Search for arr[i] + k in subarray from i+1 to n-1.
   b) If arr[i] + k found, increment count. 
5) Return count. 

int binarySearch(int arr[], int low, int high, int x)

{

    if (high >= low)

    {

        int mid = low + (high - low)/2;

        if (x == arr[mid])

            return mid;

        if (x > arr[mid])

            return binarySearch(arr, (mid + 1), high, x);

        else

            return binarySearch(arr, low, (mid -1), x);

    }

    return -1;

}

/* Returns count of pairs with difference k in arr[] of size n. */

int countPairsWithDiffK(int arr[], int n, int k)

{

    int count = 0, i;

    sort(arr, arr+n);  // Sort array elements

    /* code to remove duplicates from arr[] */

   

    // Pick a first element point

    for (i = 0; i < n-1; i++) // not good!!! can be done in O(n)

        if (binarySearch(arr, i+1, n-1, arr[i] + k) != -1)

            count++;

    return count;

}

//Sort the array

Collections.sort(list);

int num = list.get(0);

int l = 1;

int h = n-1;

int i = 1;

int count = 0;

while( i < n ) {

//For 'num' search if 'num+k' exists using binary search

while( l < h ) {

int mid = (l+h)/2;

int val = list.get(mid);

if( val == num+k) {

count++;

break;

} else if( val < num+k ) {

l = mid;

} else {

h = mid;

}

}

num = list.get(i);

i++;

l = i;

h = n-1;



}

Method 4 (Use Hashing)
We can also use hashing to achieve the average time complexity as O(n) for many cases.
1) Initialize count as 0.
2) Insert all distinct elements of arr[] in a hash map.  While inserting, ignore an element if already present in the hash map.
3) Do following for each element arr[i].
   a) Look for arr[i] + k in the hash map, if found then increment count
   b) Look for arr[i] - k in the hash map, if found then increment count
   c) Remove arr[i] from hash table. 

int countPairsWithDiffK(int arr[], int n, int k)

{

    int count = 0;  // Initialize count

    // Initialize empty hashmap.

    bool hashmap[MAX] = {false};

    // Insert array elements to hashmap

    for (int i = 0; i < n; i++)

        hashmap[arr[i]] = true;

    for (int i = 0; i < n; i++)

    {

        int x = arr[i];

        if (x - k >= 0 && hashmap[x - k])

            count++;

        if (x + k < MAX && hashmap[x + k])

            count++;

        hashmap[x] = false;

    }

    return count;

}

Method 3 (Use Self-balancing BST)
We can also a self-balancing BST like AVL tree or Red Black tree to solve this problem. Following is detailed algorithm.
1) Initialize count as 0.
2) Insert all elements of arr[] in an AVL tree. While inserting, 
   ignore an element if already present in AVL tree.
3) Do following for each element arr[i].
   a) Search for arr[i] + k in AVL tree, if found then increment count.
   b) Search for arr[i] - k in AVL tree, if found then increment count.
   c) Remove arr[i] from AVL tree. 

Time complexity of above solution is also O(nLogn) as search and delete operations take O(Logn) time for a self-balancing binary search tree.

int countPairsWithDiffK(int arr[], int n, int k)

{

    int count = 0;  // Initialize count

    // Initialize empty hashmap.

    bool hashmap[MAX] = {false};

    // Insert array elements to hashmap

    for (int i = 0; i < n; i++)

        hashmap[arr[i]] = true;

    for (int i = 0; i < n; i++)

    {

        int x = arr[i];

        if (x - k >= 0 && hashmap[x - k])

            count++;

        if (x + k < MAX && hashmap[x + k])

            count++;

        hashmap[x] = false;

    }

    return count;

}

X. Brute Force - O(N^2)

int countPairsWithDiffK(int arr[], int n, int k)

{

    int count = 0;

     

    // Pick all elements one by one

    for (int i = 0; i < n; i++)

    {      

        // See if there is a pair of this picked element

        for (int j = i+1; j < n; j++)

            if (arr[i] - arr[j] == k || arr[j] - arr[i] == k )

                  count++;

    }

    return count;

}

https://github.com/mission-peace/interview/blob/master/src/com/interview/binarysearch/CountNDistinctPairsWithDifferenceK.java
Read full article from Break the CODE!!!: Interviewstreet Challenge: Pairs