# Print Pairs with the given difference in sorted array

Given a sorted array and a number k. print all pairs in the array with difference between them is k.

Solution 1: Using Hash Map

Create a hashmap and then traverse the array. Use array elements as hash keys and enter them in hashmap. Traverse the array again and look for value k + arr[i] in hashmap. if found,then print arr[i] and arr[i]+k.

Below is the c++ implementation of the same.

```#include <iostream>
using namespace std;
#define MAX 100000

void printPairsWithDiff(int arr[], int arr_size, int diff)
{
int temp;
bool hashMap[MAX] = {0};

for(int i = 0; i < arr_size; i++)
{
hashMap[arr[i]] = 1;
}

for(int i = 0; i < arr_size; i++)
{
temp = arr[i]+diff;

if(temp>=0 && hashMap[temp] == 1)
cout<<"Pair Found: ("<<arr[i]<<","<<temp<<")"<<endl;
}
}

int main()
{
int A[] = {1,3,5,6,9};
int k = 2;
int arr_size = sizeof(A)/sizeof(A[0]);

printPairsWithDiff(A, arr_size, k);
return 0;
}
```

Time Complexity : O(N)

Solution 2 : Without additional data structure.

Take 2 indexes i and j.Initially i points to first element and j points to second element of array respectively.if difference of arr[j] and arr[i] is k then print them and increment both i and j.if difference between them is less than k then increment j else increment i.

```void printPairsWithDiff(int arr[], int arr_size, int diff)
{
int i=0,j=1;
while(i<arr_size && j<arr_size)
{
if (i != j && arr[j]-arr[i] == diff)
{
cout<<"Pair Found: ("<<arr[i]<<","<<arr[j]<<")"<<endl;
i++;
j++;
}
else if(arr[j]-arr[i]<diff)
j++;
else
i++;
}
}
```

Time Complexity : O(N)

### One Thought on “Print Pairs with the given difference in sorted array”

1. roh wang on January 24, 2016 at 5:21 am said:

we have a naive O(n2) approach using 2 for loops and simply looking for the given diff as well.
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a[j]-a[i]==diff)
{
cout<<"pairs:"<<a[i]<<","<<a[j];
}
}
}