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

Output:

(4, 1)
(5, 2)

## Java

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.

Output:

(4, 1)
(5, 2)

## Java

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 votes, average: 5.00 out of 5)

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 🙂