Pairs · Coding Gym

See the original problem on HackerRank.

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:

\( 2-1=1, 3-2=1, 4-3=1 \)

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 arr.

Constraints

\( 2 \le n \le 10^5 \)
\( 0 \lt k \lt 10^9 \)
\( 0 \lt arr[i] \lt 2^{31}-1 \)
each integer \( arr[i] \) will be unique

Output Format

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

Sample Input

5 2
1 5 3 4 2

Sample output

Explanation

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

Solutions

A quadratic solution is correct, but it’s too slow and some test cases do not pass.

To find a solution, we can turn the problem space of searching pairs into searching one element for each iteration.

We need to find i - j = k, for each i and j. This means, for each i we just need to find if i - k is in the array.

The problem turns into a searching problem where the lookup needs to be fast. We can use an efficient data struture for this purpose like tree-based maps - such as C++’s std::map or Java’s TreeMap -, hash maps, etc, or we can simply sort the original array and use binary search.

Simple binary search

We sort the input array and then we apply the idea above:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

using namespace std;

int main()
{
  int n, k;
  cin >> n >> k;
  vector<int> v(n);
  copy_n(istream_iterator<int>(cin), n, begin(v));
  sort(begin(v), end(v));

  // i - k = j
  auto cnt = 0;
  for (auto x : v)
  {
    if (binary_search(begin(v), end(v), x - k)) cnt++;
  }

  cout << cnt;
}

Using some standard algorithms:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


int main()
{
    int n, k; cin >> n >> k;
    vector<int> v(n);
    copy_n(istream_iterator<int>(cin), n, begin(v));
    sort(begin(v), end(v));
    cout << count_if(begin(v), end(v), [&](int curr){
        return binary_search(begin(v), end(v), curr-k);
    });
}

Optimized binary search

Looking at the previous solution, we notice that for each i, the binary search runs from the beginning of the array. If we change the number we search, we can start the binary search from the current position, cutting down the search space.

Instead of looking for i - k = j, we reverse the equation and look for j + k = i. Since the array is sorted, j+k is always increasing. This means it’s not possible to find i among the elements we have already looked into during the previous iterations.

Here is a working solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


int main()
{
  int n;
  cin >> n;
  int k;
  cin >> k;
  vector<int> data;
  for (size_t i = 0; i < n; i++)
  {
    int val;
    cin >> val;
    data.push_back(val);
  }
  sort(data.begin(), data.end());

  size_t count = 0;
  for (size_t i = 0; i < data.size(); ++i)
  {
    if (binary_search(data.begin() + i + 1, data.end(), data[i] + k)) count++;
  }
  cout << count;
}

Using other data structures

As said before, alternative solutions involve using other data structures such as maps, sets and dictionaries because we want to optimize finding i - k = j (or j + k = i).

Here is an elegant solution in Erlang by Giancarlo Valente:

1
2
3


pairs(K, Arr) ->
    S = sets:from_list(Arr),
    length([X || X <- Arr, sets:is_element(X + K, S)]).

The same in Python by kernelfolla:

1
2
3


def pairs(k, arr):
    s = set(arr)
    return len([x for x in arr if x+k in s])

Same patterns in C++:

1
2
3
4
5
6
7
8


int N, K; cin >> N >> K;
unordered_set<int> S{
    istream_iterator<int>(cin),
    istream_iterator<int>()};

cout << count_if(begin(S), end(S), [&](int i){
   return S.count(i-K);
});

Using arrays intersection

We can use a support array where store each sum (a[i] + k). To get how many pairs match the requirement, we can count the result from arrays intersection (input’s array and sum’s array).

Here is a solution in PHP by Roberto Peruzzo:

1
2
3
4
5


function pairs($k, $arr) {
    $sum = $arr;
    array_walk($sum, function(&$item, $key, $k) { $item += $k; }, $k);
    return count(array_intersect($arr, $sum));
}

sorting