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
|
|
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:
|
|
Using some standard algorithms:
|
|
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:
|
|
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:
|
|
The same in Python by kernelfolla:
|
|
Same patterns in C++:
|
|
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:
|
|