Find all Symmetric Pairs in an Array of Pairs

Given an array of pairs of integers, find all symmetric pairs i.e. pairs that are mirror of each other. For instance, pairs (x, y) and (y, x) are mirrors of each other.


 

For example,


Input: {3, 4}, {1, 2}, {5, 2}, {7, 10}, {4, 3}, {2, 5}

Output:

{4, 3} | {3, 4}
{2, 5} | {5, 2}

 
Naive solution would be consider every pair and check if they are mirror of each other or not. The time complexity of this solution is O(n2).

 
We can solve this problem in linear time using hashing. The idea is to consider every pair and insert the pair into a set. We also construct the mirror pair for every pair and if mirror pair if seen before (i.e. mirror pair is found in set), we print both pairs.

C++

Download   Run Code

Output:

{4, 3} | {3, 4}
{2, 5} | {5, 2}

Java

Download   Run Code

Output:

{4, 3} | {3, 4}
{2, 5} | {5, 2}

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
sahil
Guest
sahil

thanks