Check if Two Arrays Contain the Same Elements - Java

Category: Medium | Concepts used: Sorting comparison, frequency map comparison

---

Problem Statement

Given two arrays, check whether they contain the same elements with the same frequencies (order doesn’t matter).

Input : [1,2,3], [3,1,2]         Output: true
Input : [1,2,2], [1,1,2]          Output: false  (different counts of each value)

Examples (with edge scenarios)

#	Array A	Array B	Output	Why
1	[1,2,3]	[3,1,2]	true	Same elements, different order
2	[1,2,2]	[1,1,2]	false	Element frequencies don’t match (two 2’s vs two 1’s)
3	[]	[]	true	Both empty — trivially equal
4	[1,2]	[1,2,3]	false	Different lengths — can’t be equal
5	[1,1,2]	[1,2,2]	false	Same distinct values, but different counts

Common Fresher Mistake

Mistake	What happens	Fix
Just checking if both arrays contain the same distinct values (ignoring counts)	Wrongly reports true for [1,1,2] vs [1,2,2]	Must compare frequencies, not just presence — use a frequency map or sort-and-compare
Forgetting to check array lengths first	Unnecessary extra work if lengths already differ	Quick early-exit: if a.length != b.length, they can’t be equal — return false immediately

---

Before You Code: Clarify the Contract

Before choosing an algorithm, confirm whether the array may be null or empty, whether duplicates and original order matter, whether the method may modify the input, and whether the answer should contain values or original indices. These choices can change both the code and the best data structure.

Analogy: Inventory Verification

Imagine you are checking two shipping containers (arrays) to make sure they contain the exact same inventory (same items with same quantities):

• Solution 1 (Sorting): You unpack both containers, sort all products alphabetically by model number in two lines, and then walk down the lines side-by-side comparing the items one-by-one. If every slot matches perfectly, the containers are identical.
• Solution 2 (Frequency Maps): You take a clipboard and write down the barcode of every item in Container A, counting their total quantities (buildFrequencyMap(a)). You do the same for Container B on a second clipboard. If both clipboards end up with the exact same items and counts listed, you verify that the containers are identical!

---

Solution 1 — Sort Both Arrays and Compare

Intuition

If two arrays contain exactly the same elements (with the same counts), then sorting both of them should line every matching value up in the exact same positions — making a simple element-by-element comparison of the sorted versions sufficient.

import java.util.Arrays;

public class SameElementsSort {
    public static boolean haveSameElements(int[] a, int[] b) {
        if (a.length != b.length) {
            return false; // quick early exit
        }

int[] sortedA = a.clone();
        int[] sortedB = b.clone();
        Arrays.sort(sortedA);
        Arrays.sort(sortedB);

return Arrays.equals(sortedA, sortedB);
    }

public static void main(String[] args) {
        System.out.println(haveSameElements(new int[]{1,2,3}, new int[]{3,1,2})); // true
        System.out.println(haveSameElements(new int[]{1,2,2}, new int[]{1,1,2})); // false
        System.out.println(haveSameElements(new int[]{}, new int[]{}));             // true
    }
}

Output:

true
false
true

Dry Run (a=[1,2,3], b=[3,1,2])

sortedA = [1,2,3]
sortedB = [1,2,3]
Arrays.equals -> element-by-element match -> true

Interviewer’s take

This is a clean, easy-to-explain solution. It’s O(n log n) due to sorting, which is perfectly acceptable for most interview contexts. Arrays.equals() is a standard method here, not a shortcut that avoids the logic — using it is fine.

Follow-up questions you might get:

• “Can you do this without sorting, in O(n) time?” → leads to Solution 2.

---

Solution 2 — Using Frequency Maps (O(n), No Sorting)

Intuition

Instead of sorting to line up matching values, directly count how many times each value appears in array A, and separately how many times each value appears in array B. If both frequency maps are exactly identical, the arrays must contain the same elements with the same counts.

import java.util.HashMap;

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

HashMap<Integer, Integer> freqA = buildFrequencyMap(a);
        HashMap<Integer, Integer> freqB = buildFrequencyMap(b);

return freqA.equals(freqB); // HashMap.equals compares keys AND values
    }

private static HashMap<Integer, Integer> buildFrequencyMap(int[] arr) {
        HashMap<Integer, Integer> freq = new HashMap<>();
        for (int num : arr) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        return freq;
    }

public static void main(String[] args) {
        System.out.println(haveSameElements(new int[]{1,2,3}, new int[]{3,1,2})); // true
        System.out.println(haveSameElements(new int[]{1,2,2}, new int[]{1,1,2})); // false
    }
}

Output:

true
false

Dry Run (a=[1,2,2], b=[1,1,2])

freqA = {1:1, 2:2}
freqB = {1:2, 2:1}
freqA.equals(freqB)? Keys match, but values differ (1:1 vs 1:2) -> false

Interviewer’s take

This is the preferred optimized answer — O(n) time overall (building two frequency maps is linear), compared to O(n log n) for sorting. A nice detail to mention: Java’s built-in HashMap.equals() already compares both keys and values correctly, so there’s no need to manually loop and compare each key.

Follow-up questions you might get:

• “Why is this better than sorting?” → Sorting is O(n log n); building and comparing frequency maps is O(n) — a real asymptotic improvement for large arrays.
• “What if the arrays contain very large ranges of numbers?” → HashMap-based counting still works fine regardless of the value range (unlike a fixed-size counting array, which would need bounds on the values).

---

📊 Visual Flowchart

graph TD
    Start["Given Arrays a and b"] --> LengthCheck{"a.length == b.length?"}
    LengthCheck -->|No| RetFalse["Return False"]
    LengthCheck -->|Yes| InitMaps["Build freqA and freqB"]
    InitMaps --> Compare{"freqA.equals(freqB)?"}
    Compare -->|Yes| RetTrue["Return True"]
    Compare -->|No| RetFalse

---

Final Verdict — Which Solution Should You Give?

Solution 1 (sort + compare)  ──O(n log n)──►  Good, simple, acceptable
Solution 2 (frequency maps)  ──O(n)────────►   PREFERRED, more optimal

• Both solutions are considered valid — Solution 1 is perfectly fine for most interviews given its simplicity, but Solution 2 is the better answer if efficiency is discussed.

---

Quick Recap

Approach	Time	Space
Sort + Arrays.equals()	O(n log n)	O(n) for copies
Frequency maps + equals()	O(n)	O(n) for two maps