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