2 Diff - C++ Solution

1. Introduction

In this blog post, we address a common problem in array processing: finding all pairs in an unsorted integer array that have a specific difference k. The challenge is to do this efficiently using constant space, making it a test of both algorithmic ingenuity and memory management.

Problem

Given an unsorted integer array, the task is to find all pairs with a given difference k. The solution should return a set containing all distinct pairs in sorted order, and it must use constant space.

2. Solution Steps

1. Sort the array in ascending order to facilitate a linear scan for pairs.

2. Use two pointers to traverse the array and identify valid pairs.

3. Ensure that each pair is distinct and adheres to the specified difference k.

4. Add each valid pair to the set in sorted order.

5. Return the set of pairs.

3. Code Program

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

set<pair<int, int>> findPairsWithDiff(const vector<int>& nums, int k) {
    set<pair<int, int>> pairs;
    int n = nums.size();
    sort(nums.begin(), nums.end());

    int i = 0, j = 1;
    while (j < n) {
        int diff = nums[j] - nums[i];

        if (diff == k) {
            pairs.insert({nums[i], nums[j]});
            j++;
        } else if (diff < k) {
            j++;
        } else {
            i++;
        }

        if (i == j) j++;
    }

    return pairs;
}

int main() {
    vector<int> nums = {1, 5, 2, 2, 2, 5, 5, 4};
    int k = 3;
    set<pair<int, int>> result = findPairsWithDiff(nums, k);

    // Output the result
    for (const auto& p : result) {
        cout << "(" << p.first << ", " << p.second << ") ";
    }
    cout << endl;

    return 0;
}

Output:

(1, 4) (2, 5)

Explanation:

The function findPairsWithDiff identifies all pairs in the array that have a difference of k. It first sorts the array and then uses a two-pointer approach to find pairs with the required difference. The pairs are stored in a set to ensure uniqueness and sorted order. For the input array [1, 5, 2, 2, 2, 5, 5, 4] with k = 3, the distinct pairs are (1, 4) and (2, 5).