Find Pair Given Difference

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