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)