Pairs - Hacker Rank Solution

You will be given an array of integers and a target value. Determine the number of pairs of array elements that have a difference equal to a target value.

For example, given an array of [1, 2, 3, 4] and a target value of 1, we have three values meeting the condition: , , and .

Function Description

Complete the pairs function below. It must return an integer representing the number of element pairs having the required difference.

pairs has the following parameter(s):

• k: an integer, the target difference
• arr: an array of integers

Input Format

The first line contains two space-separated integers  and , the size of  and the target value.
The second line contains  space-separated integers of the array .

Constraints

• each integer  will be unique

Output Format

An integer representing the number of pairs of integers whose difference is .

Sample Input

5 2  
1 5 3 4 2  

Sample Output

3

Explanation

There are 3 pairs of integers in the set with a difference of 2: [5,3], [4,2] and [3,1] .

Pairs - Hacker Rank Solution

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.

Most programming languages already support these data structures in their library functions. For example, if you want to use a binary search tree in C++, you can use STL set; if you want to use a hash table in C++, you can use unordered_set.

It is easy to test the performance of both set and unordered_set. And you can see that unordered_set does run faster than set, which in turn validates the advantage over time complexity.

//C++
//Pairs.cpp
//Pairs
//Algorithms - Search
//Author: derekhh

#include<iostream>
#include<unordered_set>
using namespace std;

unordered_set<int> s;

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

Problem Tester's code:

#!/bin/python3

import os

# Complete the pairs function below.
def pairs(k, arr):
    a = set(arr)
    # make a set of all a[i] + k
    b = set(x + k for x in arr)
    # return the length of the intersection set
    return len(a&b)

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    nk = input().split()

    n = int(nk[0])

    k = int(nk[1])

    arr = list(map(int, input().rstrip().split()))

    result = pairs(k, arr)

    fptr.write(str(result) + '\n')

    fptr.close()