Print all unique Pairs with given Sum

Given an array of integers, and a number ‘sum’, print all unique pairs in the array whose sum is equal to ‘sum’.

Examples :

`Input : arr[] = {1, 5, 7, -1, 5}, sum = 6
Output : (1, 5), (7, -1)

Input : arr[] = {2, 5, 17, -1} sum = 7
Output : (2, 5)`

Approach - 1

• sort the array so that all duplicates resides side by side.
• when we found a pair (a,b) if either a or b has duplicate values, we will only take first occurence of the duplicate value and skips the next occurences to avoid duplicate pairs.
• now take 2 pointers left and right, left pointer starts from 0th index and right pointer from n-1th index.
• check for total 3 cases
• case-1 arr[left]+arr[right]==sum
• we found a valid pair, so we print it and move both the pointers.
• and also check whether the curr pointer(left and right) is same as previous value, if yes move ahead without doing anything on these values.
• case-2 arr[left]+arr[right]<sum
• move left pointer to get larger value
• case-3 arr[left]+arr[right]>sum
• move right pointer to get smaller value

Code

vector<vector<int>> pairSum(vector<int> &arr, int s) {
    int n = arr.size();
    sort(arr.begin(), arr.end());
    vector<vector<int>> pairs;
    int i = 0;
    int j = n - 1;

    while (i < j) {
        int sum = arr[i] + arr[j];
        if (sum == s) {
            pairs.push_back({arr[i], arr[j]});
            i++;
            j--;
            // Skip duplicates for i
            while (i < j && arr[i] == arr[i - 1]) {
                i++;
            }
            // Skip duplicates for j
            while (i < j && arr[j] == arr[j + 1]) {
                j--;
            }
        } else if (sum < s) {
            i++;
        } else {
            j--;
        }
    }

    return pairs;  
}

Time Complexity: O(N)+O(NlogN)

Approach - 2 Using Hashing

• create an hashmap that stores key-value pairs of elements and its frequencies.
• iterate through the elements
• for each element finds its complement and check whether it has been seen before.
• if it was seen before here 2 cases
• case-1 the element and its complement is same.. check its frequency. If the frequency is 1, print the pair since it can form a valid pair without duplicates.
• If the frequency is greater than 1, skip to avoid duplicates.
• case-2 If the current element and its complement are different
• Check for the Complement: If the complement exists in the hashmap, it means we have previously encountered this complement.
• Avoiding Reverse Duplicates:
• If the current element has been seen before (i.e., it’s already in the hashmap), you would be generating the pair in reverse order. To avoid printing the same pair twice (once as (a, b) and once as (b, a)), you only print the pair if it’s the first time you’re processing the current element.
• if not seen before moving ahead for searching to the next iteration, update the frequency of the element in the hashmap

// Function to print pairs with the given sum
void printPairs(int arr[], int n, int sum) {
    // Store counts of all elements in map m
    unordered_map<int, int> m;

    // Traverse through all elements
    for (int i = 0; i < n; i++) {
        // Search if a pair can be formed with arr[i].
        int rem = sum - arr[i];
        if (rem == arr[i]) {
            // Check if the complement is in the map and occurs only once
            if (m.find(rem) != m.end() && m[rem] == 1) {
                cout << "(" << rem << ", " << arr[i] << ")" << endl;
            }
        } else if (m.find(rem) != m.end() && m.find(arr[i]) == m.end()) {
            // Check if the complement is in the map and the current element is not in the map
            cout << "(" << rem << ", " << arr[i] << ")" << endl;
        }
        m[arr[i]]++; // Update the map with the current element's count
    }
}

Time Complexity: O(N)
Space Complexity: O(N)