Given an Array of Pairs Find all Symmetric Pairs in it

Difficulty Level Easy
Frequently asked in Amazon Capgemini Cisco FreeCharge Moonfrog Labs Opera Xome
Array HashViews 3774

Find all symmetric pairs – You are given some pairs of an array. You have to find out the symmetric pairs in it. The symmetric pair is said to be symmetric when in pairs say (a, b) and (c, d) in which ‘b’ is equal to ‘c’ and ‘a’ is equal to ‘d’, that is, (1, 2) is symmetric pair of (2, 1).

Example

Given an Array of Pairs Find all Symmetric Pairs in it

{{11, 20},{30,40},{4,5},{5,4},{40,30}}
(4, 5) (30, 40)

Algorithm to find all symmetric pairs

  1. Declare a HashMap.
  2. While i < n (array’s length)
    1. Set firstValue to array[i][0] and secondValue to arr[i][1].
    2. Check if the value of secondValue is not null and if the value of secondValue is equal to firstValue
    3. If true, then print secondValue and firstValue.
    4. Else put the firstValue and secondValue into Hashmap.
  3. Repeat the process from a to d till loop exists.

Explanation

We have given an array pairs, inside that array some symmetric pairs exist. The problem statement says that we have to find all symmetric pairs that exist in an array. We can simply use two loops and traverse both of the arrays one by one. But it costs us more time complexity and we can’t have an efficient code. We then try to use a better approach to sort them first in a particular order but also it takes our efficiency. So to get an efficient program we must use hashing.

By using a hashmap, we first store the pair’s first element to firstValue and pair’s second element to secondValue, we can use both of the elements of a pair as a key and a value. We will search for it in a map by comparing a key of one pair to the value of another pair and value of that same pair to the key of that of another pair.

We are going to use a hashmap let us consider  an example for given an array of pairs, Find all Symmetric Pairs in it

Example

arr={{1, 2},{30,40},{6,9},{2,1},{9,6}}

We will be storing the array’s pairs value into firstValue and secondValue and then we will be checking it.

i=0,

firstValue = arr[i][0]       //pair 1st element

secondValue = arr[i][1]  //pair 2nd element

firstValue= 1, secondValue=2

We will check for 1 if it has a value in a map and condition false so it put both of the value into the map.

Map=[{1:2}]

i=1,

firstValue = arr[i][0]       //pair 1st element

secondValue = arr[i][1]  //pair 2nd element

firstValue= 30, secondValue=40

We will check for 30 if it has a value in a map and condition false so it put both of the value into the map.

Map=[{1:2},{30:40}]

i=2,

firstValue = arr[i][0]       //pair 1st element

secondValue = arr[i][1]  //pair 2nd element

firstValue= 6, secondValue=9

We will check for 6 if it has a value in a map and condition false so it put both of the value into the map.

Map=[{1:2},{30:40},{6:9}]

i=3,

firstValue = arr[i][0]       //pair 1st element

secondValue = arr[i][1]  //pair 2nd element

firstValue= 2, secondValue=1

We will check for 1 if it has value exists in a map and it does exists as ‘2’, then we will check, if secondValue’s element is equal to firstValue and this condition also satisfy.

So we print (1, 2)

Map=[{1:2},{30:40},{6:9}]

i=4,

firstValue = arr[i][0]       //pair 1st element

secondValue = arr[i][1]  //pair 2nd element

firstValue= 9, secondValue=6

We will check for 6 if it has value exists in a map and it does exist as ‘9’, then we will check if secondValue’s element is equal to firstValue and this condition also satisfy.

So we print (1, 2), (6, 9)

Map=[{1:2},{30:40},{6:9}]

Code

C++ Program to find all symmetric pairs

#include<unordered_map>
#include<iostream>
using namespace std;
void getSymmetricPair(int arr[][2], int row)
{
    unordered_map<int, int> myMap;

    for (int i = 0; i < row; i++)
    {
        int firstValue = arr[i][0];
        int secondValue = arr[i][1];

        if (myMap.find(secondValue) != myMap.end() && myMap[secondValue] == firstValue)
        {
            cout << "(" << secondValue << ", " << firstValue << ")"<<" ";
        }
        else
        {
            myMap[firstValue] = secondValue;
        }
    }
}
int main()
{
    int arr[5][2]= {{11,20},{30,40},{4,5},{5,4},{40,30}};
    getSymmetricPair(arr, 5);
}

(4, 5) (30, 40)

Java Program to find all symmetric pairs

import java.util.HashMap;
class pairSymmetrics
{
    static void getSymmetricPair(int arr[][])
    {
        HashMap<Integer, Integer> hashmap = new HashMap<Integer, Integer>();

        for (int i = 0; i < arr.length; i++)
        {
            int firstValue = arr[i][0];
            int secondValue = arr[i][1];
            Integer val = hashmap.get(secondValue);

            if (val != null && val == firstValue)
            {
                System.out.print("(" + secondValue + ", " + firstValue + ")" + " ");
            }
            else
            {
                hashmap.put(firstValue, secondValue);
            }
        }
    }

    public static void main(String arg[])
    {
        int arr[][]= {{11,20},{30,40},{4,5},{5,4},{40,30}};
        getSymmetricPair(arr);

    }
}

(4, 5) (30, 40)

Complexity Analysis

Time Complexity

O(n) where “n” is the number of elements in the array. Since we have used a HashMap we can perform insertion/deletion/searching in O(1) time.

Space Complexity

O(n) where “n” is the number of elements in the array. Since we have stored elements in the map. The space complexity is linear.

References

Translate »