Program to find all symmetric pairs in an array | faceprep

Program to find all symmetric pairs in an array is discussed here. Two pairs (p,q) and (r,s) are said to be symmetric when q is equal to r and p is equal to s. For example, (5,10) and (10,5) are symmetric pairs.

For example, 

Consider two a 2D array,

Input:

arr [6] [2] = {{1, 2}, {3, 4}, {5, 6}, {2, 1}, {4, 3},{10,11}}

Output:

{1,2} and {2,1} are symmetric
{3,4} abd {4,3} are symmetric

This problem can be solved in two different ways.

Method 1: Using two loops, one loop to traverse the pairs and the other loop to check if similar pair is existing.

Method 2: An efficient way to solve this problem is to use hashing. Insert each array pairs into the hash table with the first element of the pair as the key and the second element as the value. Traverse the hash table to check if the pairs are found again.

Algorithm to find all symmetric pairs in an array

  1. Input the array from the user.
  2. Use two loops.
  3. One loop for traversing the array and the other loop to check if symmetric pair is found in the array.
  4. If symmetric pair is found, print the pairs.

Program to find all symmetric pairs in an array is given below.

// C program to find all symmetric pairs in an array

#include <stdio.h>

void symmetric_array_pair(int arr1[], int arr2[], int m, int n)
{
int i,j;
for(i=0;i<m;i++)
{
for(j=0;j<m;j++)
{
if(arr1[i] == arr2[j] && arr1[j]== arr2[i])
{
printf(“(%d,%d)\t”,arr1[i],arr1[j]);
continue;
}
}
}
}

int main()
{
int m,n;
scanf(“%d%d”,&m,&n);
int i,j;
int arr1[m],arr2[n];

for(i=0;i<m;i++)
{
scanf(“%d”,&arr1[i]);
}

for(i=0;i<m;i++)
{
scanf(“%d”,&arr2[i]);
}

symmetric_array_pair(arr1,arr2,m,n);

return 0;
}

// C++ program to find all symmetric pairs in an array

#include <iostream>
using namespace std;

void symmetric_array_pair(int arr1[], int arr2[], int m, int n)
{
int i,j;
for(i=0;i<m;i++)
{
for(j=0;j<m;j++)
{
if(arr1[i] == arr2[j] && arr1[j]== arr2[i])
{
cout << “(” <<arr1[i]<< “,”<<arr1[j]<<“)”<<“\t”;
continue;
}
}
}
}

int main()
{
int m,n;
cin >> m >>n;
int i,j;
int arr1[m],arr2[n];

for(i=0;i<m;i++)
{
cin >> arr1[i];
}

for(i=0;i<m;i++)
{
cin >> arr2[i];
}

symmetric_array_pair(arr1,arr2,m,n);

return 0;
}

// Java program to find all symmetric pairs in an array

import java.util.*;
public class Main
{
static void symmetric_array_pair(int arr1[], int arr2[], int m, int n)
{
int i,j;
for(i=0;i<m;i++)
{
for(j=0;j<m;j++)
{
if(arr1[i] == arr2[j] && arr1[j]== arr2[i])
{
System.out.print(“(” + arr1[i] + “,”+ arr1[j] + “)”);
continue;
}
}
}
}

public static void main(String[] args)
{
int arr1[] = {1,2,3,4,5};
int arr2[] = {2,1,4,3,6};
int m = arr1.length;
int n = arr2.length;
symmetric_array_pair(arr1,arr2,m,n);
}
}

# Python program to find all symmetric pairs in an array

def symmetric_array_pairs(arr1,arr2,m,n):
for i in range(0,m):
for j in range(0,n):
if(arr1[i] == arr2[j] and arr1[j]== arr2[i]):
print(“(“,arr1[i],”,”,arr1[j],”)”, end = ” “)

arr1 = []
arr2 = []
arr1 = [1,2,3,4,5]
arr2 = [2,1,4,3,6]
symmetric_array_pairs(arr1, arr2, len(arr1),len(arr2))

Time complexity: O(n^2)

Algorithm to find symmetric pairs in an array using hashing

  1. Input the array from the user.
  2. From all the array pairs, the first element is used as the key and the second element is used as the value.
  3. Traverse all the pairs one by one.
  4. For every pair, check if its second element is found in the hash table.
  5. If yes, then compare the first element with the value of the matched entry of the hash table.
  6. If the value and the first element match, it is displayed as a symmetric pair.
  7.  Else, insert the first element as the key and second element as value and repeat the same.

 

Program to find all symmetric pairs in an array using hashing is given below.

// C++ program to find all symmetric pairs in an array using hashing

#include<bits/stdc++.h>
using namespace std;

void find_symmetric_pairs(int arr[][2], int row)
{
// Create an empty hashMap
unordered_map<int, int> hashMap;

// Traverse through the array
for (int i = 0; i < row; i++)
{
// First element as key and second as value from each pair
int first = arr[i][0];
int second = arr[i][1];

// If found and value in hash matches with first element of this pair, we found symmetry
if (hashMap.find(second) != hashMap.end() && hashMap[second] == first)
cout << “(” << second << “, ” << first << “)” << ” “;

else // Else put the second element of this pair in hash table
hashMap[first] = second;
}
}

int main()
{
int arr[5][2];
arr[0][0] = 1; arr[0][1] = 2;
arr[1][0] = 3; arr[1][1] = 4;
arr[2][0] = 5; arr[2][1] = 6;
arr[3][0] = 2; arr[3][1] = 1;
arr[4][0] = 4; arr[4][1] = 3;
cout << “Symmetric pairs : “;
find_symmetric_pairs(arr, 5);
}

// Java program to find all symmetric pairs in a given array
import java.util.HashMap;

class Main
{

// Print all pairs that have a symmetric counterpart
static void find_symmetric_pairs(int arr[][])
{
// Create an empty hashMap
HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();

// Traverse through the array
for (int i = 0; i < arr.length; i++)
{
// First element as key and second element as value for each pair
int first = arr[i][0];
int second = arr[i][1];

// Look for second element of this pair in hashtable
Integer val = hashMap.get(second);

// If found and value in hash matches with first element of this pair, we found symmetry
if (val != null && val == first)
System.out.print(“(” + second + “, ” + first + “)” + ” “);

else // Else put second element of this pair in hash table
hashMap.put(first, second);
}
}

public static void main(String arg[])
{
int arr[][] = new int[5][2];
arr[0][0] = 1; arr[0][1] = 2;
arr[1][0] = 3; arr[1][1] = 4;
arr[2][0] = 5; arr[2][1] = 6;
arr[3][0] = 2; arr[3][1] = 1;
arr[4][0] = 4; arr[4][1] = 3;
System.out.print(“Symmetric pairs : “);
find_symmetric_pairs(arr);
}
}

Output:

symmetric pairs in an array

Time complexity: O(n)