Uniquely identify an array of numbers whose order doesn't matter

Question

Let's say I have these 3 integer arrays:

int[] a = {1, 2, 3};
int[] b = {3, 4, 5};
int[] c = (2, 1, 3};

I'm looking for the most efficient code that will consider a the same as c (because they contain the same numbers but in a different order), but consider a different from b, and b different from c.

I know I can sort them all so that c becomes {1, 2, 3} and therefore the same as a, but I'm comparing hundreds of arrays with more than three numbers each and I don't want my program to sort each one of them, I'm thinking there must be a better way.

Also, taking the sum, for example, wouldn't work because the sum of numbers in {1, 4, 5} is the same as that of numbers in {1, 3, 6}.

And the product wouldn't work either because the product of numbers in {1, 2, 6} is the same as that of numbers in {1, 3, 4}.

Answer 1

Sorting is an O(nlog(n) operation (in the worst case). You could, instead, have an O(n) solution by running over both arrays and just counting the elements in it:

public static boolean hasSameElements(int[] a, int[] b) {
    return countElements(a).equals(countElements(b);)
}

private static Map<Integer, Long> countElements(int[] arr) {
    return Arrays.stream(arr)
                 .boxed()
                 .collect(Collectors.groupingBy(Function.identity(), 
                          Collectors.counting()));
}

EDIT:
While it won't change the big-O notation of the algorithm, a slightly less elegant solution could perform better for non-matching arrays by failing fast:

public static boolean hasSameElements(int[] a, int[] b) {
    if (a.length != b.length) {
        return false;
    }

    Map<Integer, Long> popCount =
            Arrays.stream(a)
                  .mapToObj(Integer::valueOf)
                  .collect(Collectors.groupingBy(Function.identity(), 
                           Collectors.counting()));

    for (int elem : b) {
        Long count = popCount.get(elem);
        if (count == null) {
            return false;
        }
        count--;
        if (count == 0L) {
            popCount.remove(elem);
        } else {
            popCount.put(elem, count);
        }
    }

    return popCount.isEmpty();
}