Two pairs (a, b) and (c, d) are said to be symmetric if c is equal to b and a is equal to d. For example, (10, 20) and (20, 10) are symmetric. Given an array of pairs find all symmetric pairs in it.
It may be assumed that the first elements of all pairs are distinct.
Example:
Input: arr[] = {{11, 20}, {30, 40}, {5, 10}, {40, 30}, {10, 5}}
Output: Following pairs have symmetric pairs
(30, 40)
(5, 10)
Naive approach: The idea is to use two nested loops, one for selecting one pair and the second for searching the other symmetric pair in the given array.
The pair are said to be symmetric if arr[i][0] == arr[j][1] and arr[i][1] == arr[j][0] satisfy.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
void findSymPairs( int arr[][2], int row)
{
for ( int i = 0; i < row; i++) {
for ( int j = i + 1; j < row; j++) {
if (arr[i][0] == arr[j][1]
and arr[i][1] == arr[j][0])
{
cout << "(" << arr[i][0] << ", "
<< arr[i][1] << ")" << endl;
}
}
}
}
int main()
{
int arr[5][2];
arr[0][0] = 11;
arr[0][1] = 20;
arr[1][0] = 30;
arr[1][1] = 40;
arr[2][0] = 5;
arr[2][1] = 10;
arr[3][0] = 40;
arr[3][1] = 30;
arr[4][0] = 10;
arr[4][1] = 5;
cout << "Following pairs have symmetric pairs\n" ;
findSymPairs(arr, 5);
}
|
Java
public class GFG
{
public static void findSymPairs( int [][] arr, int row)
{
for ( int i = 0 ; i < row; i++) {
for ( int j = i + 1 ; j < row; j++) {
if (arr[i][ 0 ] == arr[j][ 1 ]
&& arr[i][ 1 ] == arr[j][ 0 ]) {
System.out.print( "(" );
System.out.print(arr[i][ 0 ]);
System.out.print( ", " );
System.out.print(arr[i][ 1 ]);
System.out.print( ")" );
System.out.print( "\n" );
}
}
}
}
public static void main(String[] args)
{
int [][] arr = new int [ 5 ][ 2 ];
arr[ 0 ][ 0 ] = 11 ;
arr[ 0 ][ 1 ] = 20 ;
arr[ 1 ][ 0 ] = 30 ;
arr[ 1 ][ 1 ] = 40 ;
arr[ 2 ][ 0 ] = 5 ;
arr[ 2 ][ 1 ] = 10 ;
arr[ 3 ][ 0 ] = 40 ;
arr[ 3 ][ 1 ] = 30 ;
arr[ 4 ][ 0 ] = 10 ;
arr[ 4 ][ 1 ] = 5 ;
System.out.print(
"Following pairs have symmetric pairs\n" );
findSymPairs(arr, 5 );
}
}
|
Python3
def findSymPairs(arr, row):
for i in range ( 0 , row):
for j in range (i + 1 , row):
if (arr[i][ 0 ] = = arr[j][ 1 ] and arr[i][ 1 ] = = arr[j][ 0 ]):
print ( "(" ,arr[i][ 0 ], "," ,arr[i][ 1 ], ")" )
if __name__ = = '__main__' :
arr = [[ 0 for i in range ( 2 )]
for i in range ( 5 )]
arr[ 0 ][ 0 ], arr[ 0 ][ 1 ] = 11 , 20
arr[ 1 ][ 0 ], arr[ 1 ][ 1 ] = 30 , 40
arr[ 2 ][ 0 ], arr[ 2 ][ 1 ] = 5 , 10
arr[ 3 ][ 0 ], arr[ 3 ][ 1 ] = 40 , 30
arr[ 4 ][ 0 ], arr[ 4 ][ 1 ] = 10 , 5
findSymPairs(arr, 5 )
|
C#
using System;
public class GFG
{
public static void findSymPairs( int [,] arr, int row)
{
for ( int i = 0; i < row; i++) {
for ( int j = i + 1; j < row; j++) {
if (arr[i,0] == arr[j,1]
&& arr[i,1] == arr[j,0]) {
Console.Write( "(" );
Console.Write(arr[i,0]);
Console.Write( ", " );
Console.Write(arr[i,1]);
Console.Write( ")" );
Console.Write( "\n" );
}
}
}
}
public static void Main(String[] args)
{
int [,] arr = new int [5,2];
arr[0,0] = 11;
arr[0,1] = 20;
arr[1,0] = 30;
arr[1,1] = 40;
arr[2,0] = 5;
arr[2,1] = 10;
arr[3,0] = 40;
arr[3,1] = 30;
arr[4,0] = 10;
arr[4,1] = 5;
Console.Write(
"Following pairs have symmetric pairs\n" );
findSymPairs(arr, 5);
}
}
|
Javascript
function findSymPairs( arr, row)
{
for ( var i = 0; i < row; i++) {
for ( var j = i + 1; j < row; j++) {
if (arr[i][0] === arr[j][1]
&& arr[i][1] === arr[j][0])
{
console.log( "(" + arr[i][0] + ", "
+ arr[i][1] + ")\n" );
}
}
}
}
var arr = new Array(5);
for ( var i=0;i<5;i++)
arr[i] = new Array(2);
arr[0][0] = 11;
arr[0][1] = 20;
arr[1][0] = 30;
arr[1][1] = 40;
arr[2][0] = 5;
arr[2][1] = 10;
arr[3][0] = 40;
arr[3][1] = 30;
arr[4][0] = 10;
arr[4][1] = 5;
console.log( "Following pairs have symmetric pairs\n" );
findSymPairs(arr, 5);
|
Output
Following pairs have symmetric pairs
(30, 40)
(5, 10)
Time Complexity: O(n2) .
Auxiliary Space: O(1)
A Better Solution is to use sorting. Sort all pairs by the first element. For every pair, do a binary search for the second element in the given array, i.e., check if the second element of this pair exists as the first element in the array. If found, then compare the first element of the pair with the second element.
C++
#include<bits/stdc++.h>
using namespace std;
int binarySearch(vector<pair< int , int >> arr, int i, int j, int n){
int mid = (i+j)/2;
if (i>j){
return -1;
}
if (arr[mid].second == n){
return mid;
}
else if (arr[mid].second>n){
return binarySearch(arr ,i, mid-1, n);
}
else if (arr[mid].second<n){
return binarySearch(arr, mid+1, j, n);
}
}
void sol(vector<pair< int , int >> arr){
sort(arr.begin(), arr.end());
for ( int i=0; i<arr.size(); i++){
int idx = binarySearch(arr, 0, arr.size()-1, arr[i].first);
if (arr[idx].first == arr[i].second && idx != -1){
cout<<arr[idx].first<< " " <<arr[idx].second<<endl;
}
}
}
int main(){
vector<pair< int , int >> vec = {{11, 20}, {30, 40}, {5, 10}, {40, 30}, {10, 5}};
sol(vec);
return 0;
}
|
Java
import java.util.*;
public class Main {
static int binarySearch( int [][] arr, int i, int j, int n) {
int mid = (i+j)/ 2 ;
if (i > j){
return - 1 ;
}
if (arr[mid][ 1 ] == n){
return mid;
}
else if (arr[mid][ 1 ] > n){
return binarySearch(arr, i, mid - 1 , n);
}
else if (arr[mid][ 1 ] < n){
return binarySearch(arr, mid + 1 , j, n);
}
return - 1 ;
}
static void findSymPairs( int [][] arr, int row) {
Arrays.sort(arr, Comparator.comparingInt(a -> a[ 0 ]));
for ( int i= 0 ; i<row; i++){
int idx = binarySearch(arr, 0 , row- 1 , arr[i][ 0 ]);
if (idx != - 1 && arr[idx][ 0 ] == arr[i][ 1 ]){
System.out.println(arr[idx][ 0 ] + " " + arr[idx][ 1 ]);
}
}
}
public static void main(String[] args) {
int [][] arr = new int [ 5 ][ 2 ];
arr[ 0 ][ 0 ] = 11 ;
arr[ 0 ][ 1 ] = 20 ;
arr[ 1 ][ 0 ] = 30 ;
arr[ 1 ][ 1 ] = 40 ;
arr[ 2 ][ 0 ] = 5 ;
arr[ 2 ][ 1 ] = 10 ;
arr[ 3 ][ 0 ] = 40 ;
arr[ 3 ][ 1 ] = 30 ;
arr[ 4 ][ 0 ] = 10 ;
arr[ 4 ][ 1 ] = 5 ;
findSymPairs(arr, 5 );
}
}
|
Python3
def binarySearch(arr, i, j, n):
mid = (i + j) / / 2 ;
if (i > j):
return - 1 ;
if (arr[mid][ 1 ] = = n):
return mid
elif (arr[mid][ 1 ] > n):
return binarySearch(arr, i, mid - 1 , n)
elif (arr[mid][ 1 ] < n):
return binarySearch(arr, mid + 1 , j, n)
def findSymPairs(arr, row):
arr.sort()
for i in range (row):
idx = binarySearch(arr, 0 , row - 1 , arr[i][ 0 ])
if (arr[idx][ 0 ] = = arr[i][ 1 ] and idx ! = - 1 ):
print (arr[idx][ 0 ], " " ,arr[idx][ 1 ])
if __name__ = = '__main__' :
arr = [[ 0 for i in range ( 2 )]
for i in range ( 5 )]
arr[ 0 ][ 0 ], arr[ 0 ][ 1 ] = 11 , 20
arr[ 1 ][ 0 ], arr[ 1 ][ 1 ] = 30 , 40
arr[ 2 ][ 0 ], arr[ 2 ][ 1 ] = 5 , 10
arr[ 3 ][ 0 ], arr[ 3 ][ 1 ] = 40 , 30
arr[ 4 ][ 0 ], arr[ 4 ][ 1 ] = 10 , 5
findSymPairs(arr, 5 )
|
C#
using System;
using System.Collections.Generic;
class Program
{
static void FindReversedPairs(List<( int , int )> arr)
{
Dictionary< int , int > pairsMap = new Dictionary< int , int >();
foreach ( var pair in arr)
{
if (pairsMap.ContainsKey(pair.Item2) && pairsMap[pair.Item2] == pair.Item1)
{
Console.WriteLine(pair.Item1 + " " + pair.Item2);
}
else
{
pairsMap[pair.Item1] = pair.Item2;
}
}
}
static void Main()
{
List<( int , int )> pairs = new List<( int , int )>
{
(11, 20),
(30, 40),
(5, 10),
(40, 30),
(10, 5)
};
FindReversedPairs(pairs);
Console.ReadLine();
}
}
|
Javascript
function binarySearch(arr, i, j, n) {
let mid = Math.floor((i + j) / 2);
if (i > j) {
return -1;
}
if (arr[mid][1] === n) {
return mid;
} else if (arr[mid][1] > n) {
return binarySearch(arr, i, mid - 1, n);
} else if (arr[mid][1] < n) {
return binarySearch(arr, mid + 1, j, n);
}
}
function findPairsWithReverseOrder(arr) {
arr.sort((a, b) => a[0] - b[0]);
for (let i = 0; i < arr.length; i++) {
let idx = binarySearch(arr, 0, arr.length - 1, arr[i][0]);
if (idx !== -1 && arr[idx][0] === arr[i][1]) {
console.log(arr[idx][0], arr[idx][1]);
}
}
}
function main() {
const arr = [[11, 20], [30, 40], [5, 10], [40, 30], [10, 5]];
findPairsWithReverseOrder(arr);
}
main();
|
Time Complexity: O(n Log n).
Auxiliary Space: O(log n), The extra space is used in recursion call stack.
An Efficient Solution is to use Hashing. The first element of the pair is used as the key and the second element is used as the value. The idea is to traverse all pairs one by one. For every pair, check if its second element is in the hash table. If yes, then compare the first element with the value of the matched entry of the hash table. If the value and the first element match, then we found symmetric pairs. Else, insert the first element as a key and the second element as a value.
Below is the implementation of the above approach:
C++
#include<bits/stdc++.h>
using namespace std;
void findSymPairs( int arr[][2], int row)
{
unordered_map< int , int > hM;
for ( int i = 0; i < row; i++)
{
int first = arr[i][0];
int sec = arr[i][1];
if (hM.find(sec) != hM.end() && hM[sec] == first)
cout << "(" << sec << ", " << first << ")" <<endl;
else
hM[first] = sec;
}
}
int main()
{
int arr[5][2];
arr[0][0] = 11; arr[0][1] = 20;
arr[1][0] = 30; arr[1][1] = 40;
arr[2][0] = 5; arr[2][1] = 10;
arr[3][0] = 40; arr[3][1] = 30;
arr[4][0] = 10; arr[4][1] = 5;
cout<< "Following pairs have symmetric pairs\n" ;
findSymPairs(arr, 5);
}
|
Java
import java.util.HashMap;
class SymmetricPairs {
static void findSymPairs( int arr[][])
{
HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();
for ( int i = 0 ; i < arr.length; i++)
{
int first = arr[i][ 0 ];
int sec = arr[i][ 1 ];
Integer val = hM.get(sec);
if (val != null && val == first)
System.out.println( "(" + sec + ", " + first + ")" );
else
hM.put(first, sec);
}
}
public static void main(String arg[])
{
int arr[][] = new int [ 5 ][ 2 ];
arr[ 0 ][ 0 ] = 11 ; arr[ 0 ][ 1 ] = 20 ;
arr[ 1 ][ 0 ] = 30 ; arr[ 1 ][ 1 ] = 40 ;
arr[ 2 ][ 0 ] = 5 ; arr[ 2 ][ 1 ] = 10 ;
arr[ 3 ][ 0 ] = 40 ; arr[ 3 ][ 1 ] = 30 ;
arr[ 4 ][ 0 ] = 10 ; arr[ 4 ][ 1 ] = 5 ;
findSymPairs(arr);
}
}
|
Python3
def findSymPairs(arr, row):
hM = dict ()
for i in range (row):
first = arr[i][ 0 ]
sec = arr[i][ 1 ]
if (sec in hM.keys() and hM[sec] = = first):
print ( "(" , sec, "," , first, ")" )
else :
hM[first] = sec
if __name__ = = '__main__' :
arr = [[ 0 for i in range ( 2 )]
for i in range ( 5 )]
arr[ 0 ][ 0 ], arr[ 0 ][ 1 ] = 11 , 20
arr[ 1 ][ 0 ], arr[ 1 ][ 1 ] = 30 , 40
arr[ 2 ][ 0 ], arr[ 2 ][ 1 ] = 5 , 10
arr[ 3 ][ 0 ], arr[ 3 ][ 1 ] = 40 , 30
arr[ 4 ][ 0 ], arr[ 4 ][ 1 ] = 10 , 5
findSymPairs(arr, 5 )
|
C#
using System;
using System.Collections.Generic;
public class SymmetricPairs
{
static void findSymPairs( int [,]arr)
{
Dictionary< int , int > hM = new Dictionary< int , int >();
int val = 0;
for ( int i = 0; i < arr.GetLength(0); i++)
{
int first = arr[i, 0];
int sec = arr[i, 1];
if (hM.ContainsKey(sec))
val = hM[sec];
if (val != 0 && val == first)
Console.WriteLine( "(" + sec + ", " + first + ")" );
else
hM.Add(first, sec);
}
}
public static void Main(String []arg)
{
int [,]arr = new int [5, 2];
arr[0, 0] = 11; arr[0, 1] = 20;
arr[1, 0] = 30; arr[1, 1] = 40;
arr[2, 0] = 5; arr[2, 1] = 10;
arr[3, 0] = 40; arr[3, 1] = 30;
arr[4, 0] = 10; arr[4, 1] = 5;
findSymPairs(arr);
}
}
|
Javascript
<script>
function findSymPairs(arr)
{
let hM = new Map();
for (let i = 0; i < arr.length; i++)
{
let first = arr[i][0];
let sec = arr[i][1];
let val = hM.get(sec);
if (val != null && val == first)
document.write( "(" + sec + ", " + first + ")<br>" );
else
hM.set(first, sec);
}
}
let arr = new Array(5);
for (let i = 0; i < arr.length; i++)
{
arr[i] = new Array(2);
for (let j = 0; j < 2; j++)
{
arr[i][j] = 0;
}
}
arr[0][0] = 11; arr[0][1] = 20;
arr[1][0] = 30; arr[1][1] = 40;
arr[2][0] = 5; arr[2][1] = 10;
arr[3][0] = 40; arr[3][1] = 30;
arr[4][0] = 10; arr[4][1] = 5;
findSymPairs(arr);
</script>
|
Output
Following pairs have symmetric pairs
(30, 40)
(5, 10)
Time Complexity: O(n), where n is the size of the given array.
Auxiliary Space: O(n)
This article is contributed by Shivam Agrawal.