Find all Symmetric Pairs in the array of pairs

In this article, we will solve the problem: “Find all Symmetric Pairs in the array of pairs”

Problem Statement: Given an array of pairs, find all the symmetric pairs in the array.

Examples:

Example 1:
Input: (1,2),(2,1),(3,4),(4,5),(5,4)
Output: (2,1) (5,4)
Explanation: Since (1,2) and (2,1) are symmetric pairs and (4,5) and (5,4) are symmetric pairs.

Example 2:
Input: (1,5),(2,3),(4,2),(5,1),(2,4)
Output: (2,4) (5,1)
Explanation: Since (1,5) and (2,4) are symmetric pairs and (5,1) and (4,2) are symmetric pairs.

Solution 1: Brute force

Intuition: For every pair check in the vector pair if the symmetric pair is present or not.

Approach:

First use a for loop and traverse through every pair in the vector.
Then use another for loop and check if the symmetric pair of that pair is present in the rest of the vector or not.
If the symmetric pair is present print the pair and break from the second for loop.so as to avoid repetitive printing of answers in case of duplicate pair.
If the symmetric pair is not present,move to the next pair.

Code:

C++ Code

#include<bits/stdc++.h>

using namespace std;
int main() {
  int n = 5;
 
  int arr[][2] = {{1, 2}, {2, 1}, {3, 4}, {4, 5}, {5, 4}}; 
  cout << "The Symmetric Pairs are: " << endl;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (arr[j][0] == arr[i][1] && arr[j][1] == arr[i][0]) {
        cout << "(" << arr[i][1] << " " << arr[i][0] << ")" << " ";
        break;
      }
    }
  }

}

Output:

The Symmetric Pairs are:
(2 1) (5 4)

Time Complexity: O(N*N).

Space Complexity: O(1).

Java Code

import java.util.*;
public class Main {
    public static void main(String args[]) {
        int n = 5;
        int arr[][] = {{1, 2}, {2, 1}, {3, 4}, {4, 5}, {5, 4}};
        System.out.println("The symmetric pairs are: ");
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (arr[j][0] == arr[i][1] && arr[j][1] == arr[i][0]) {
                    System.out.print("(" + arr[i][1] + " " + arr[i][0] + ")" + " ");
                    break;
                }
            }
        }
    }
}

Output:

The Symmetric Pairs are:
(2 1) (5 4)

Time Complexity: O(N*N).

Space Complexity: O(1).

Solution: Time optimized

Intuition: We will store the pairs in a hash map and then check if the symmetric pair exists or not.

Approach:

Store pairs in the hashmap.
Let “first” be the first element of the pair and “second” be the second element of the pair.
While iterating through the pairs we will check if {second,first} exists by using map.
If {second,first} exists then print the pair,else store it in the map.

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n = 5;
	int arr[5][2] = {{1, 2}, {2, 1}, {3, 4}, {4, 5}, {5, 4}};
	unordered_map<int, int>mp;
	cout<<"The Symmetric Pairs are: "<<endl;
	for (int i = 0; i < n; i++) {
		int first = arr[i][0];
		int second = arr[i][1];
		
		//if {second,first} existed previously,print them.
		if (mp.find(second) != mp.end() && mp[second] == first) {
			cout << "(" << first << " " << second << ")" << " ";
		}
		//else store them in the map
		else {
			mp[first] = second;
		}
	}
}

Output:

The Symmetric Pairs are:
(2 1) (5 4)

Time Complexity: O(N).

Space Complexity: O(N), for using a hashmap.

Java Code

import java.util.HashMap;
public class Main {
  public static void main(String args[]) {
    
    int arr[][] = {{1, 2}, {2, 1}, {3, 4}, {4, 5}, {5, 4}};

    HashMap < Integer, Integer > mp = new HashMap < Integer, Integer > ();
    System.out.println("The Symmetric Pairs are: ");
    for (int i = 0; i < arr.length; i++) {
      int first = arr[i][0];
      int second = arr[i][1];
      if (mp.get(second) != null && mp.get(second) == first) {
        System.out.print("("+first + " " + second+") ");
      } else {
        mp.put(first, second);
      }
    }

  }
}

Output:

The Symmetric Pairs are:
(2 1) (5 4)

Time Complexity: O(N).

Space Complexity: O(N), for using a hashmap.

Special thanks to Pranav Padawe for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article