Given an array of N distinct values, how to find the number of pairs with a difference of K?
For example, given an array [3, 1, 4, 2, 5] and K= 2, there are 3 pairs with a difference of 2. Namely {1,3}, {2,4}, {3,5}.
One obvious solution could be to examine each possible pair and count the number of pairs with the given difference. (This is similar to my previous post). But this algorithm runs in O(n2) time. If you are solving it in a competition, you most probably get a Time Limit Exceeded (TLE) error.
Let us look at more efficient solutions.
Solution 1:
Sort the array first using any algorithm like Quick sort or Merge sort or Heap sort. This takes O( n log n ) time. The algorithm is as follows.
- Take two indices and point them to first and second elements.
- Repeat the following steps until any index reaches the end of the array
- If the difference matches, increment count and increment both the indices
- If the difference is less than required value, increment second index
- Otherwise increment first index.
The algorithm takes O(n) time. The overall time complexity is O(n log n). It does not take any extra space.
Solution 2:
Using additional data structure like a set or a map.
- Store all the array elements into a set.
- For each element in the array do the following.
- If the set contains array[i]+diff or array[i]-diff, increment the diff count.
- Remove array[i] from the set.
This approach runs in O(n) time but takes O(n) additional space for the set.