Two Pointers: Given an array and a value k, return the count of pairs with k difference

Problem Statement:

Given an array and a value k, return the count of pairs with k difference

Example:

Input: arr = [1, 2, 3, 4] k = 1

Output: 3

Explanation:

[1, 2], [2, 3], [3, 4] all are having difference of 1.

Solution 1: Bruteforce Approach

Take 2 loops and check all the possible pairs in the array.

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

Solution 2: Two pointer approach

Sort the array and then use the two pointer technique to find the pairs with given difference.

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

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int solution_2 (vector<int>& nums, int k) 
{
    sort(nums.begin(), nums.end());

    int result = 0;
    int n = nums.size();
    int i = 0, j = 1;

    while (i < n && j < n) 
    {
        if (i != j && nums[j] - nums[i] == k) 
        {
            result++;
            i++;
            j++;

            // Skip duplicates
            while (i < n && nums[i] == nums[i - 1]) 
                i++;

            while (j < n && j < n && nums[j] == nums[j - 1]) 
                j++;

        } 
        else if (nums[j] - nums[i] < k) 
        {
            j++;
        } 
        else 
        {
            i++;
            if (i == j) j++;
        }
    }
    return result;
}


int solution_1 (vector<int> &arr, int k) 
{
    int n = arr.size();
    int result = 0;

    for (int i = 0; i < n; i++) 
    {
        for (int j = i + 1; j < n; j++) 
        {

            if (abs(arr[i] - arr[j]) == k) 
            {
                result += 1;
            }
        }
    }
    return result;
}


int main() 
{

    vector<int> arr = {1, 2, 3, 4};
    int k = 1;

    cout << solution_1(arr, k)<<endl;

    cout << solution_2(arr, k);

    return 0;
}

Output

3
3