Compare all elements in an array against each other in Java

One of the most common requests when processing an array is to compare each element in an array against every other element. You can imagine it as you want to take the 1st array element and compare it with every other element, then take the 2nd array element and compare it with every other element and so on and on.

We will write the following code examples in Java. As input example, let’s have a simple Java array array with 5 integer elements as method input for our arrayComparison(final int[] arr). Here is the Java code:

final int[] array = new int[]{1, 2, 3, 4, 5};
public void arrayComparison(final int[] arr);

So let’s write a simple solution for all element comparison. There is no other way than just loop trough array and take each element individually and compare it with the rest of an array. Here is the code which does exactly that:

for (int i = 0; i < arr.length; i++) {
    for (int j = 0; j < arr.length; j++) {
        // Comparison code
        System.out.println(arr[i] + " " + arr[j]);
    }
}

And this is the Java code outcome:

1 - 1   2 - 1   3 - 1   4 - 1   5 - 1
1 - 2   2 - 2   3 - 2   4 - 2   5 - 2
1 - 3   2 - 3   3 - 3   4 - 3   5 - 3
1 - 4   2 - 4   3 - 4   4 - 4   5 - 4
1 - 5   2 - 5   3 - 5   4 - 5   5 - 5

From the output, we see that we compare every element with every other element in the array.

Is it the most effective solution we can come with? Definitely no! Looping through elements 2 - 3 is the same as looping through 3 - 2, isn't it?

We can slightly optimize this solution by making a check on every iteration and omitting self-comparing elements. Here is the improved code:

for (int i = 0; i < arr.length; i++) {
    for (int j = i; j < arr.length; j++) {
        // Comparison code
        System.out.println(arr[i] + " " + arr[j]);
    }
}

And this is overall Java code output:

1 - 1
1 - 2   2 - 2
1 - 3   2 - 3   3 - 3
1 - 4   2 - 4   3 - 4   4 - 4
1 - 5   2 - 5   3 - 5   4 - 5   5 - 5

In this solution, we see that we do not need to compare the same elements, for example, 1 - 1 etc.

We can push optimization again little bit further and by making a check on every iteration omit self-reflecting elements. Here is more optimized code:

for (int i = 0; i < arr.length; i++) {
    for (int j = i; j < arr.length; j++) {
        if(arr[i] != arr[j]) {
            // Comparison code
            System.out.println(arr[i] + " " + arr[j]);
        }
    }
}

And this is overall Java code output:

1 - 2
1 - 3   2 - 3
1 - 4   2 - 4   3 - 4
1 - 5   2 - 5   3 - 5   4 - 5

This way, we get precisely the comparison pairs we were looking for.

However, there is still a way how to optimize this solution. First, we still loop through the identical elements; but we omit them with the if check.

Is there a way how to rewrite and optimize this solution? Yes, it is!

We can improve the existing solution with the start of comparison from the point of element one after the current point on the second level iteration.

Here is the solution:

for (int i = 0; i < arr.length; i++) {
    for (int j = i +  1; j < arr.length; j++) {
        // Comparison code
        System.out.println(arr[i] + " " + arr[j]);
    }
}

And this is overall Java code output:

1 - 2
1 - 3   2 - 3
1 - 4   2 - 4   3 - 4
1 - 5   2 - 5   3 - 5   4 - 5

Note: Real trick of this solution is on its last iteration. When we finish 3 - 4 we jump to 4 element. However inner loop is 5 = arr.length therefore is not valid, loop terminates and and no print is pushed to System output.