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

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 🙂

Get great deals at Amazon