Sorting: Given an unsorted array and a value x, you need to check if a pair exist for given difference

Problem Statement:

You are given an unsorted array and a value x.

You need to find if there exits a pair with absolute diffrence x.

Example:

Input:

arr = [1, 3, 2, 5, 4] x = 2

Output: Yes

Solution 1: Bruteforce approach

In this approach, we take nested loop.

Then we go through all the possible pairs in the array.

Time Complexity: O(n*n)
Space Complexity: O(1)

Solution 2: Sorting and two pointers approach

In this approach, we first sort the array.

Then we use 2 pointer approach to solve the problem.

Then if the difference between arr[i] and arr[j] is less than x, then increment j else increment i.

Time Complexity: O(nlogn)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool solution_1(vector<int> &arr, int x) 
{
    int n = arr.size();
    
    for (int i = 0; i < n; i++) 
    {
        for (int j = i + 1; j < n; j++) 
        {
            if (abs(arr[i] - arr[j]) == x) 
            {
                return true;
            }
        }
    }
    
    return false;
}



bool solution_2(vector<int> &arr, int x) 
{
    int n = arr.size();
    
    sort(arr.begin(), arr.end());
    
    int j = 1;
    
    for (int i=0; i<n; i++) 
    {

        while (j<n && arr[j]-arr[i] < x) j++;
        
        if (j<n && i != j && arr[j]-arr[i] == x) 
        	return true;
    }
    
    return false;
}


int main()
{
    vector <int> arr = { 1, 3, 2, 5, 4};
    int x = 2;
    
    if(solution_1(arr, x))
    {
    	cout<<"True";
    }
    else
    {
    	cout<<"False";
    }

    cout<<endl;

    if(solution_2(arr, x))
    {
    	cout<<"True";
    }
    else
    {
    	cout<<"False";
    }

    return 0;
}

Output

True
True