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

Output:

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

## Java

Output:

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

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.

Output:

(1, 4)
(2, 5)

## Java

Output:

(1, 4)
(2, 5)

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

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 🙂

Subscribe
Notify of
Guest
Karan

In the second method, it should be

Otherwise it will go out of the loop since you’re traversing till n and checking for `i+1`. Thanks.

Guest
Michal

If array is sorted, then there is no need to look for arr[i] + diff.

Guest