Find pairs with given difference k in the array

Given an unsorted array of integers, print all pairs with given difference k in it.

 

For example,


Input:
arr = [1, 5, 2, 2, 2, 5, 5, 4]
k = 3

Output:
(2, 5) and (1, 4)

 


 

Naive solution would be to consider every pair in given array and return if desired difference is found.
The time complexity of this solution would be O(n2).
 

We can use set to solve this problem in linear time. The idea is to insert each element of the array arr[i] in a set. We also checks if element (arr[i]-diff) or (arr[i]+diff) already exists in the set or not. If the element is seen before, we print the pair (arr[i], arr[i]-diff) or (arr[i]+diff, arr[i]).

 
C++ implementation –
 

Download   Run Code

Output:

(2, 5)
(2, 5)
(2, 5)
(2, 5)
(2, 5)
(1, 4)

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n). The problem with above approach is that this method prints duplicates pairs.
 


 

How to handle duplicates?

 

We can handle duplicates pairs by sorting the array first and then skipping adjacent similar elements.

 
C++ implementation –
 

Download   Run Code

Output:

(1, 4)
(2, 5)

 
The time complexity of above solution is O(nlogn) and auxiliary space used by the program is O(n).

 

 
 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂