Find all symmetric pairs in an array of pairs

Posted in

Find all symmetric pairs in an array of pairs

Vinay Khatri
Last updated on September 26, 2022

    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:

    Tags:
    array

    Leave a Comment on this Post

    0 Comments