Find all symmetric pairs in an array of pairs

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:

• Print a two-dimensional view of a Binary Tree
• In-place vs out-of-place algorithms
• Quicksort algorithm using Hoare’s partitioning scheme
• Sort elements by their frequency and index
• Nth root of M
• Find MSB
• Find MSB in O(1)
• Python Take list as an input from a user
• Delete Nodes And Return Forest
• Majority Element