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

(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 🙂

Subscribe
Notify of
Guest

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

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

Guest

It is needed. Run the code once.

Guest

what if k== 0?

Guest
bart2019

First code works fine as it contains duplicates. Second won’t work since we’re skipping duplicates.

Guest

Duplication is removed in O(n)