Hashing: Given an array, find two non overlapping pairs having equal sum

Problem Statement:

You are given an array.

You need to find 2 non overlapping pairs whose sum are equal.

Example:

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

Output: [2, 3], [4, 1]

Solution:

Simple solution is to generate the sum of all the pairs and see if any 2 pair have the same sum.

We will use Map to solve the problem.

We will store the sum as the key and the corresponding value will be the pair of indices.

We will generate all the possible pairs and insert the sum into the map.

Then if the sum is found, then we will check if the pairs are not overlapping, we print the result.

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

Code Solution

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

typedef pair<int, int> Pair;

void solution(vector<int> arr)
{

    int n = arr.size();

    unordered_map<int, vector<Pair> > map;

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

            int sum = arr[i] + arr[j];

            if (map.find(sum) != map.end()) 
            {

                for (auto pair : map.find(sum)->second) 
                {
                    int m = pair.first, n = pair.second;

                    if ((m != i && m != j) && (n != i && n != j)) 
                    {
                        cout << "First pair(" << arr[i] << ", "
                             << arr[j] << ")"<<endl;
                        cout << "Second Pair("
                             << arr[m] << ", " << arr[n] << ")";
                        return;
                    }
                }
            }

            map[sum].push_back({ i, j });
        }
    }

    cout << "No pairs found";
}

int main()
{
    vector<int> arr = { 1, 2, 3, 5, 4, 1 };

    solution(arr);

    return 0;
}

Output

First pair(2, 3)
Second Pair(1, 4)