Java return symmetric pairs from a 2D array-CodePudding

If I have a 2D array:

input[][] = { {"A", "B"}, {"C", "D"}, {"B", "A"}, {"C", "E"} }

I want an algorithm that returns

{("A", "B")} or {("B", "A")}

I know there's a solution using HashMap but I want to solve this without. It doesn't need to be the most efficient solution. I want to implement it in O(n log n) time so I don't want to use HashMap. I was thinking of sorting the input array and comparing the elements but I don't know how to implement it. Can anyone offer some help?

CodePudding user response：

Brute force

There’s the brute force approach: For each pair see if the reverse of it is also there. So when you have (A, B), see if you can find (B, A) (which in your example you can). When next you have (C, D), see if you can find (D, C) (this time you cannot). Use nested loops. In the outer loop iterate through the pairs. In the inner loop again iterate through the pairs. If the pair from the inner loop is the reverse of the one from the outer loop, print both pairs.

The approach has time complexity O(n ^ 2) (possibly obvious).

Happy coding.

More efficient: sort the pairs first

Sorting the pairs before you begin will allow you to use binary search for the reverse pair. Sort by first member, then by second member. In your example the sorted order will be

(A, B), (B, A), (C, D), (C, E)

Again iterate over the pairs. When you got (A, B), use binary search for finding (B, A). When you got (C, D), search for (D, C). I should come after (C, E) in the sorted order, and since there is nothing there, the pair cannot be found.

This latter approach should have time complexity O(n log n) provided that you use a good sorting algorithm.

CodePudding user response：

By HashSet

static String[] findSymmetricPairByHashSet(String[][] input) {
    record Entry(String a, String b) {}
    Set<Entry> set = new HashSet<>();
    for (String[] a : input) {
        Entry p = new Entry(a[1], a[0]);
        if (set.contains(p))
            return new String[] {p.a, p.b};
        set.add(new Entry(a[0], a[1]));
    }
    return null;
}

By TreeSet

static String[] findSymmetricPairByTreeSet(String[][] input) {
    Set<String[]> set = new TreeSet<>(Arrays::compare);
    for (String[] a : input) {
        if (set.contains(a))
            return a;
        set.add(new String[] {a[1], a[0]});
    }
    return null;
}

By Sort

static String[] findSymmetricPairBySort(String[][] input) {
    Arrays.sort(input, Arrays::compare);
    for (String[] a : input)
        if (Arrays.binarySearch(input, new String[] {a[1], a[0]},
            Arrays::compare) >= 0)
            return a;
    return null;
}

test:

public static void main(String[] args) throws IOException {
    String[][] input = {{"A", "B"}, {"C", "D"}, {"B", "A"}, {"C", "E"}};
    System.out.println(Arrays.toString(findSymmetricPairByHashSet(input)));
    System.out.println(Arrays.toString(findSymmetricPairByTreeSet(input)));
    System.out.println(Arrays.toString(findSymmetricPairBySort(input)));
}

output:

[A, B]
[B, A]
[A, B]