Find Pairs with 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++

Download   Run Code

Output:

(4, 1)
(5, 2)

Java

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++

Download   Run Code

Output:

(4, 1)
(5, 2)

Java

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

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
foobar
Guest

It should be Arrays.binarySearch(A, A[i] -diff) >= 0 based on Javadoc.