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

C++

Download   Run Code

Output:

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

Java

Download   Run Code

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.

C++

Download   Run Code

Output:

(1, 4)
(2, 5)

Java

Download   Run Code

Output:

(1, 4)
(2, 5)

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

 

 
 
Thanks for reading.

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 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Karan
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.

Michal
Guest

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

Aditya
Guest

It is needed. Run the code once.

Allen
Guest

what if k== 0?

bart2019
Guest

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

Y103
Guest

Duplication is removed in O(n)