Given an unsorted array of integers, print all pairs with given difference k in it without using any extra space.

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

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <bits/stdc++.h> using namespace std; // Function to find pair with given difference in the array // This method handles duplicates in the array void findPair(int arr[], int n, int diff) { // sort array in ascending order sort(arr, arr + n); // do for each element in the array for (int i = 0; i < n; i++) { // to avoid printing duplicates (skip adjacent duplicates) while (i < n && arr[i] == arr[i+1]) i++; // perform binary search for element (arr[i] - diff) if (binary_search(arr, arr + n, arr[i] - diff)) // STL binary search cout << "(" << arr[i] << ", " << arr[i] - diff << ")\n"; } } // Find pairs with given difference k in the array int main() { int arr[] = { 1, 5, 2, 2, 2, 5, 5, 4}; int diff = 3; int n = sizeof(arr) / sizeof(arr[0]); findPair(arr, n, diff); return 0; } |

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

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#include <bits/stdc++.h> using namespace std; // Function to find pair with given difference in the array // This method handles duplicates in the array void findPair(int arr[], int n, int diff) { // sort array in ascending order sort(arr, arr + n); // maintain two indices in the array int i = 0, j = 0; // run till end of array is reached while (i < n && j < n) { // to avoid printing duplicates while (i < n && arr[i] == arr[i+1]) i++; while (j < n && arr[j] == arr[j+1]) j++; // increment i if current difference is more than the desired difference if (arr[j] - arr[i] > diff) i++; // increment j if current difference is less than the desired difference else if (arr[j] - arr[i] < diff) j++; // print the pair and increment both i, j if current difference is same // as the desired difference else { cout << "(" << arr[j] << ", " << arr[i] << ")\n"; i++, j++; } } } // Find pairs with given difference k in the array int main() { int arr[] = { 1, 5, 2, 2, 2, 5, 5, 4 }; int diff = 3; int n = sizeof(arr) / sizeof(arr[0]); findPair(arr, n, diff); return 0; } |

** Output: **<

(4, 1)

(5, 2)

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

**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