Given an array Arr[]  containing n elements and a number k, check if there exists a pair of elements in the array whose difference is k. print 1 if exits else -1

Example:

```Input: arr[] = {5, 20, 3, 2, 50, 80}, n = 78
Output: 1
as the difference of 80 and 2 is 78

Input: arr[] = {90, 70, 20, 80, 50}, n = 45
Output: 1
as no such pair exits with difference 45```

method 1: using two loops:

simple procedure is to use two loops and check if the difference exits or not

```int pairdiff(int arr[],int n,int k)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(a[i]-a[j]==k)
return 1;
}
}

return -1;
}
```

Time complexity : O(n^2)
space complexity:O(1)

method 2: using sorting and two pointer approch:

step 1: sort the array

step 2:  take two index variables i and j, initialize them as 0 and 1 respectively. Now run a linear loop.  If arr[j] – arr[i] is equal to k we will return 1,If arr[j] – arr[i] is smaller than n, we need to look for greater arr[j], so increment j. If arr[j] – arr[i] is greater than n, we need to look for greater arr[i], so increment i.

```int pairdiff(int arr[],int n,int k)
{
int i = 0;
int j = 0;

// Search for a pair
while (i < n && j < n)
{
if (arr[j] - arr[i] == k)
{
return 1;
}
else if (arr[j]-arr[i] < k)
j++;
else
i++;
}

return -1;
}```

Time complexity : O(nlogn)
space complexity:O(1)

method 2: using unordered_map

1) store all array elements in unordered_map
2)now traverse through the array and check if the element with value equal to arr[i]-k is present or not in map
3) if present return 1
4)else it will return -1

```int pairdiff(int arr[],int n,int k)
{
//declare a unordered_map
unordered_map<int,int>m;

//store all array elements in unordered_map
for(int i=0;i<n;i++)
m[arr[i]];

//now traverse through the array
for(int i=0;i<n;i++)
{
//check if the element with value equal
//to arr[i]-k is present or not in map
if(m.find(arr[i]-k)!=m.end())
return 1;

}

return -1;

}
```

Time complexity : O(n)
space complexity:O(n)  , as we are using extra space for using map

darkmode