Find all symmetric pairs in an array of pairs

By | November 28, 2021

Problem

Given an array of pairs, find all symmetric pairs in it. Symmetric pairs are two pairs (a, b) and (b, a) for two arbitrary integers a and b.

Sample Input

[(2, 3), (3, 2), (4, 5), (5, 6)]

Sample Output

(2,3) (3,2)

Approach

We can create a hashmap in which key will be the first element of the pair and value would be the second element of each pair. We traverse through the array and check if the current pair’s second element is present in hashmap. If it is present, we check if the value of this key is equal to the first element of the current pair. If yes, we found the symmetric pair.

This approach works in O(N) time and O(N) auxiliary space.

C++ Programming

#include<bits/stdc++.h>
using namespace std;
void solve(int arr[][2], int n)
{
    // Creates an empty hashmap
    unordered_map<int, int> mp;

    for (int i = 0; i < n; i++)
    {
        int one = arr[i][0];
        int two = arr[i][1];
        if (mp.find(two) != mp.end() && mp[two] == one)
        { 
            //if we found the other pair
            cout << "(" << one << ", " << two << ")" <<endl;
            cout << "(" << two << ", " << one << ")" <<endl;
        }

        else
            mp[one] = two;
    }
}

int main()
{
    int arr[4][2] = {{1,2}, {2,1}, {4,3}, {4, 5}};
    solve(arr, 4);
}

Output

(2, 1)
(1, 2)

Python Programming

def solve(arr, n):
    mp = dict()

   for i in range(n):
        one = arr[i][0]
        two = arr[i][1]

        if (two in mp.keys() and mp[two] == one):
            print("(", two,",", one, ")")
            print("(", one,",", two, ")")
        else: 
            mp[one] = two

arr = [[1,2], [2,1], [4,3], [4,5]]
solve(arr, 4)

Output

(1, 2)
(2, 1)

Java Programming

import java.util.HashMap;

class Solution {

    static void solve(int arr[][])
    {
        HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();

        for (int i = 0; i < arr.length; i++)
        {
            int one = arr[i][0];
            int two = arr[i][1];
            
            Integer temp = mp.get(two);

            if (temp != null && temp == one){
            System.out.println("(" + two + ", " + one + ")");
            System.out.println("(" + one + ", " + two + ")");
            }
                
            else 
            mp.put(one, two);
        }
    }

    public static void main(String arg[])
    {
        int arr[][] = new int[4][2];
        arr[0][0] = 1; arr[0][1] = 2;
        arr[1][0] = 2; arr[1][1] = 1;
        arr[2][0] = 4; arr[2][1] = 3;
        arr[3][0] = 4; arr[3][1] = 5;
        solve(arr);
    }
}

Output

(1, 2)
(2, 1)

People are also reading: 

Vamware
Author: Vinay

I am a Full Stack Developer with a Bachelor's Degree in Computer Science, who also loves to write technical articles that can help fellow developers.

Leave a Reply

Your email address will not be published. Required fields are marked *