Find Symmetric Pairs in an Array

You're given a list of pairs of integers. Two pairs (a, b) and (c, d) are symmetric if a == d and b == c, meaning one is the other reversed. Report every symmetric pair, listing each match once, at the moment its second half is found.

Example

Text

Input:  [(1, 2), (3, 4), (5, 9), (4, 3), (9, 5)]
Output: [(4, 3), (9, 5)]
Explanation: (4, 3) mirrors the earlier (3, 4), and (9, 5) mirrors the earlier (5, 9).

Brute force: compare every pair with every earlier pair

For each pair j, look at every earlier pair i < j and check whether it's the mirror of pair j. A pair is stored as an int[] of length 2 in this version, so a[0] is the first value and a[1] the second.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static List<String> symmetricPairs(int[][] pairs) {
        List<String> result = new ArrayList<>();
        for (int j = 0; j < pairs.length; j++) {
            int a = pairs[j][0];
            int b = pairs[j][1];
            for (int i = 0; i < j; i++) {
                if (pairs[i][0] == b && pairs[i][1] == a) {
                    result.add("(" + a + ", " + b + ")");
                    break;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(symmetricPairs(new int[][]{{1, 2}, {3, 4}, {5, 9}, {4, 3}, {9, 5}}));
    }
}

Output

[(4, 3), (9, 5)]

Time: O(n²). Space: O(1) besides the output.

Optimal: remember the pairs you've seen

Walk the list once. For each pair (a, b):

If (b, a) has already been seen, report (a, b).
Record (a, b) as seen.

An int[] cannot be stored in a HashSet by value, because arrays compare by identity. A record is a short class declaration whose equals and hashCode compare all fields, so Pair works as a set element.

Walkthrough:

pair	mirror	mirror seen?	seen after
(1, 2)	(2, 1)	no	{(1,2)}
(3, 4)	(4, 3)	no	{(1,2), (3,4)}
(5, 9)	(9, 5)	no	{(1,2), (3,4), (5,9)}
(4, 3)	(3, 4)	yes: report (4, 3)	+ (4,3)
(9, 5)	(5, 9)	yes: report (9, 5)	+ (9,5)

Java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
    record Pair(int a, int b) {
        @Override
        public String toString() {
            return "(" + a + ", " + b + ")";
        }
    }

    static List<Pair> symmetricPairs(Pair[] pairs) {
        Set<Pair> seen = new HashSet<>();
        List<Pair> result = new ArrayList<>();
        for (Pair p : pairs) {
            if (seen.contains(new Pair(p.b(), p.a()))) {
                result.add(p);
            }
            seen.add(p);
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(symmetricPairs(new Pair[]{new Pair(1, 2), new Pair(3, 4), new Pair(5, 9), new Pair(4, 3), new Pair(9, 5)}));
        System.out.println(symmetricPairs(new Pair[]{new Pair(7, 7), new Pair(1, 2), new Pair(7, 7)}));
        System.out.println(symmetricPairs(new Pair[]{}));
    }
}

Output

[(4, 3), (9, 5)]
[(7, 7)]
[]

Time: O(n). Space: O(n) for the set.

Checking before inserting means a pair can't match itself. (7, 7) is its own mirror, so it's only reported when it appears a second time.

An alternative with a HashMap<Integer, Integer> (first to second) works only if each first element appears at most once. The set of records has no such restriction.

Edge cases

Empty input: no pairs.
Repeated pairs: (1, 2), (2, 1), (2, 1) reports (2, 1) twice, once for each occurrence that has a mirror before it.