HackerRank: Pair

HackerRank: Pair
Given N integers, count the number of pairs of integers whose difference is K.

The first observation we can make is that we don't need to enumerate all N^2 pairs and then check whether the pairs of integers have a difference of K.
What we simply need to do is - for each integer N, check whether the original array contains N-K and N+K. In fact, we can iterate over each number N in the original array and check whether N+K exists in the same array. So basically we need a data structure supporting fast membership inquiry.
Two of the most popular data structures supporting this operation are binary search tree and hash table. The former supports O(logN) time complexity, while the latter supports O(1) time complexity.
https://github.com/tbindi/hackerrank/blob/master/Solution.java
X. Use Haset
O(n) time and O(n) space solution
1. Keep a hash table(HashSet would suffice) to keep the elements already seen while passing through array once.
2. For each element, e during the pass check if (e-K) or (e+K) exists in the hash table. If exists then increment a count.
3. Add the scanned element in the hash table.

public static int diffPairs(final int[] A, final int K) {
    final HashSet<Integer> hs = new HashSet<Integer>();
    int count = 0;

    for (int i = 0; i < A.length; i++) {
        if (hs.contains(A[i] - K)) {
            count++;
        }
        if (hs.contains(A[i] + K)) {
            count++;
        }

        hs.add(A[i]);
    }
    return count;
}

https://github.com/tbindi/hackerrank/blob/master/Solution.java

	public static void main(String[] args) { Scanner in = new Scanner(System.in);
	int n = in.nextInt();
	int k = in.nextInt();
	Set<Integer> set = new HashSet<Integer>();
	for (int i = 0; i < n; i++) {
	set.add(in.nextInt());
	}
	findPairs(set, k);
	}
	private static void findPairs(Set<Integer> set, int k) {
	int pairs = 0;
	for(Integer i: set){
	pairs += set.contains(i+k) ? 1:0;
	}
	System.out.println(pairs);
	}

X. Sort and Two Pointers
http://www.zrzahid.com/pairs-with-a-difference-of-k/
https://github.com/wvbraun/HackerRank/blob/master/src/main/java/code/prep/hackerrank/algorithms/search/Pairs.java

	private static void pairs(int[] ls, int k) {
	int pairs = 0;
	Arrays.sort(ls);
	int i = 0;
	int j = 1;
	while (j < ls.length)
	{
	if (ls[j] - ls[i] == k)
	{
	++i;
	++j;
	++pairs;
	}
	else if (ls[j] - ls[i] > k)
	{
	++i;
	}
	else
	{
	++j;
	}
	}
	System.out.println(pairs);
	}

Pre-sort + binary search
O(nlgk) time O(1) space solution

1. Sort the array , O(nlgn)
2. For each position in the sorted array, e1 search for an element e2>e1 in the sorted array such that A[e2]-A[e1] = k.

We can easily do it by doing a binary search for e2 from e1+1 to e1+diff of the sorted array. Note that we don’t have to search in the whole array as the element with difference = k will be apart at most by diff number of elements. Thus each search will be only O(logK). So for the whole scan time is O(nlgk). The overall complexity is O(nlgn)+O(nlgk). If k>n then time complexity of this algorithm is O(nlgk) wit O(1) space.

private static int binarySearch(final int[] A, int l, int r, final int key) {
    int m = -1;

    while (l <= r) {
        m = (l + r) / 2;

        if (A[m] == key) {
            return m;
        } else if (key < A[m]) {
            r = m - 1;
        } else {
            l = m + 1;
        }
    }

    return -1;
}

public static int diffPairs2(final int[] A, final int diff) {
    Arrays.sort(A);
    int count = 0;
    int matchKey = 0;
    int matchIndex = -1;

    for (int i = 0; i < A.length; i++) {
        // if we are in e1=A[i] and searching for a match=e2, e2>e1 such that e2-e1= diff then e2=e1+diff
        // So, potential match to search in the rest of the sorted array is match = A[i] + diff; We will do a binary
        // search. Also note that the math should be at most |diff| element away to right of the current position i
        matchKey = A[i] + diff;
        matchIndex = binarySearch(A, Math.min(i + 1, A.length - 1), Math.min(i + diff, A.length - 1), matchKey);
        count += (matchIndex != -1) ? 1 : 0;
    }

    return count;
}

https://dhruvpancholi.wordpress.com/2015/01/28/hackerrank-pairs-solution-in-c-2/

    sort(a, a+N);

    int count = 0;

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

        if(binary_search(a, a+N, a[n]+K)) count++;

    printf("%d", count);

http://topblogcoder.com/hackerrank-pairs

    static void pairs(int[] input2, int diff)

    {

        Array.Sort(input2);

            int count = 0;

            for(int a = 0; a < input2.Length - 1; a++)

            {

                    for(int b = a + 1; b < input2.Length; b++)

                    {

                        int x = Math.Abs(input2[b] - input2[a]);

                        if(x == diff)

                             count++;

                         if(x > diff)

                             break;

                    }

            }

        Console.WriteLine(count);

    }

int main()
{
    int n, k, val;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> val;
        s.insert(val);
    }
    int ans = 0;
    for (unordered_set<int>::iterator it = s.begin(); it != s.end(); ++it)
        if (s.find(*it + k) != s.end()) ans++;
    cout << ans << endl;
    return 0;
}

http://blog.refu.co/?p=1182

http://www.zrzahid.com/pairs-with-a-difference-of-k/

Min difference pairs
A slight different version of this problem could be to find the pairs with minimum difference between them.

For example, in A=[-1, 15, 8, 5, 2, -14, 6, 7] min diff pairs are={(5,6), (6,7), (7,8)}.

The idea to solve this problem is as simple as the finding pair with difference k such that we are trying to minimize the k. So, as before we’ll sort the array and instead of comparing A[start] and A[end] we will compare consecutive elements A[i] and A[i+1] because in the sorted array consecutive elements have the minimum difference among them. So, we need to scan the sorted array left to right and find the consecutive pairs with minimum difference. Below is the O(nlgn) time code with O(1) space.

public static List<String> minDiffPairs(final int[] A) {
    ArrayList<String> pairs = new ArrayList<String>();
    int minDiff = Integer.MAX_VALUE;

    Arrays.sort(A);
    for (int i = 0; i < A.length - 1; i++) {
        if (Math.abs(A[i + 1] - A[i]) < minDiff) {
            pairs = new ArrayList<String>();
            pairs.add("(" + A[i] + "," + A[i + 1] + ")");
            minDiff = Math.abs(A[i + 1] - A[i]);
        } else if (Math.abs(A[i + 1] - A[i]) == minDiff) {
            pairs.add("(" + A[i] + "," + A[i + 1] + ")");
        }
    }

    return pairs;
}

Read full article from HackerRank - Pairs | TopBlogCoderTopBlogCoder