Find pairs with given difference k in the array | Constant space solution

Given an unsorted array of integers, print all pairs with given difference k in it without using any extra space.

 

For example,


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

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

 


 

We have discussed a linear time solution in previous post that takes O(n) extra space. We inserted each element of the array arr[i] in a set and check 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]).
 

We can avoid using extra space by performing binary search for element (arr[i] – diff) or (arr[i] + diff) instead of using hashing.

 
C++ implementation –
 

Download   Run Code

Output:

(4, 1)
(5, 2)

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


 

Alternate approach –

 

The idea is somewhat similar to finding pair with given sum in the array. But instead of starting from two end-points of the array, we start from beginning of the sorted array.

 
C++ implementation –
 

Download   Run Code

Output:

(4, 1)
(5, 2)

 
The time complexity of above solution is O(nlogn) and auxiliary space used by the program is O(1).
 
 
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 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz