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