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.

Output:

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

Java

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).

(1 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂