Check if Two Arrays Are Equal

Given two arrays of the same length, return true if they are equal as multisets: they contain the same values, each with the same count, possibly in a different order.

Example

Text

Input:  [3, 8, 9, 1], [9, 1, 8, 3]    Output: true
Input:  [1, 2, 2], [1, 1, 2]          Output: false   (2 appears twice vs once)

Brute force: sort both

Two arrays are permutations of each other exactly when their sorted versions are identical.

Java

import java.util.Arrays;

public class Main {
    static boolean areEqual(int[] a, int[] b) {
        int[] x = a.clone();
        int[] y = b.clone();
        Arrays.sort(x);
        Arrays.sort(y);
        return Arrays.equals(x, y);
    }

    public static void main(String[] args) {
        System.out.println(areEqual(new int[]{3, 8, 9, 1}, new int[]{9, 1, 8, 3}) + " " + areEqual(new int[]{1, 2, 2}, new int[]{1, 1, 2}));
    }
}

Output

true false

Time: O(n log n). Space: O(n) for the copies (O(1) extra if the arrays may be sorted in place). Arrays.equals compares two arrays element by element; == on arrays compares references.

Optimal: count with a HashMap

Count each value of a up, and each value of b down, in a HashMap<Integer, Integer>. The arrays are equal if every count ends at zero. Returning early as soon as a count would go negative saves the final check for most unequal inputs.

Java

import java.util.HashMap;
import java.util.Map;

public class Main {
    static boolean areEqual(int[] a, int[] b) {
        if (a.length != b.length) return false;
        Map<Integer, Integer> counts = new HashMap<>();
        for (int x : a) {
            counts.merge(x, 1, Integer::sum);
        }
        for (int x : b) {
            int left = counts.getOrDefault(x, 0);
            if (left == 0) return false; // x appears more often in b than in a
            counts.put(x, left - 1);
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(areEqual(new int[]{3, 8, 9, 1}, new int[]{9, 1, 8, 3}) + " " + areEqual(new int[]{1, 2, 2}, new int[]{1, 1, 2}));
        System.out.println(areEqual(new int[]{}, new int[]{}) + " " + areEqual(new int[]{1}, new int[]{1, 1}));
    }
}

Output

true false
true false

Time: O(n) on average. Space: O(n).

With equal lengths, no count can end above zero if none went below it: b would need fewer elements than a. That's why the length check up front makes the loop over b sufficient.

Edge cases

Different lengths: false immediately.
Empty arrays: equal.
Floating-point values: a HashMap<Double, Integer> works, but Double.equals treats NaN as equal to NaN and 0.0 as different from -0.0. Arrays.sort on a double[] uses the same ordering.