Check If Two Arrays Are Equal in C++

Quick answer: Two arrays are “equal” in this problem if they contain the same elements with the same frequencies, regardless of order. The cleanest solution is to count the frequency of every element in the first array with a hash map, then subtract while walking the second array — O(N) time and O(N) space. Sorting both arrays and comparing index by index also works in O(N log N) time with no extra memory beyond the sort.

This is one of the most common warm-up questions in coding interviews at service companies and start-ups alike, because it tests whether you reach for the right data structure instead of brute force. Below you will find the full problem statement, three approaches from slowest to fastest, a complexity comparison, working Python and C++ code with test cases, the edge cases interviewers probe, and the follow-up questions that usually come next.

Problem statement

Given two arrays A and B, each of size N, determine whether they are equal. Two arrays are considered equal if they contain the same set of elements, and if an element repeats, it repeats the same number of times in both arrays. The order of elements does not matter. Return 1 (true) if the arrays are equal and 0 (false) otherwise.

Example 1

Input:  N = 5
        A[] = {6, 1, 7, 4, 9}
        B[] = {1, 4, 7, 9, 6}
Output: 1
Explanation: Both arrays contain exactly the elements 1, 4, 6, 7 and 9, each once.

Example 2

Input:  N = 3
        A[] = {17, 12, 51}
        B[] = {21, 14, 5}
Output: 0
Explanation: None of the elements match.

Example 3 (duplicates matter)

Input:  N = 4
        A[] = {1, 2, 2, 3}
        B[] = {1, 2, 3, 3}
Output: 0
Explanation: Same distinct values, but 2 appears twice in A and once in B.

Constraints are typically 1 ≤ N ≤ 10^5 and element values up to 10^9, which rules out an O(N^2) solution for the largest inputs. If the two arrays have different lengths, they cannot be equal — check that first.

Approach 1: Brute force with a visited array

The naive idea: for every element of A, scan B for an unused matching element and mark it as used. If any element of A fails to find a partner, the arrays differ. This is correct and handles duplicates, but it is O(N^2) time — for N = 10^5 that is 10 billion comparisons, far too slow. It is worth stating in an interview only as a baseline before you improve it.

Approach 2: Sort and compare

Sorting puts equal multisets into identical order. Sort both arrays, then walk them together; the first mismatch at any index proves inequality.

1. If len(A) != len(B), return false.
2. Sort A and B.
3. For each index i from 0 to N-1, if A[i] != B[i] return false.
4. Return true.

Sorting dominates at O(N log N); the comparison pass is O(N). Space is O(1) extra if you sort in place (or O(log N) for the recursion stack of a typical quicksort/introsort). The downside is that it mutates the input — copy first if the caller needs the original order.

Approach 3: Frequency hash map (optimal)

Count how many times each value appears in A. Then for each value in B, decrement its count; if the value is missing or its count is already zero, the arrays are not equal. Because both arrays have the same length, finishing the loop without failure guarantees every count is exactly zero.

1. If lengths differ, return false.
2. Build freq from A: freq[x] += 1 for each x.
3. For each y in B: if freq[y] is absent or zero, return false; else freq[y] -= 1.
4. Return true.

Each insertion and lookup is O(1) on average, giving O(N) time and O(N) extra space for the map. This is the answer interviewers expect.

Complexity comparison

Python implementation

Python’s collections.Counter is a frequency map with equality built in, so the optimal solution is a one-liner. The explicit version below mirrors the algorithm you would describe in an interview.

from collections import Counter


def are_equal_sorting(a: list[int], b: list[int]) -> bool:
    """O(N log N) time. Uses sorted() so the inputs are not mutated."""
    if len(a) != len(b):
        return False
    return sorted(a) == sorted(b)


def are_equal_hashmap(a: list[int], b: list[int]) -> bool:
    """O(N) time, O(N) space. Explicit frequency-count version."""
    if len(a) != len(b):
        return False
    freq: dict[int, int] = {}
    for x in a:
        freq[x] = freq.get(x, 0) + 1
    for y in b:
        if freq.get(y, 0) == 0:
            return False
        freq[y] -= 1
    return True


def are_equal_counter(a: list[int], b: list[int]) -> bool:
    """Same algorithm, idiomatic Python."""
    return len(a) == len(b) and Counter(a) == Counter(b)


if __name__ == "__main__":
    tests = [
        ([6, 1, 7, 4, 9], [1, 4, 7, 9, 6], True),
        ([17, 12, 51], [21, 14, 5], False),
        ([1, 2, 2, 3], [1, 2, 3, 3], False),
        ([], [], True),
        ([1, 2], [1, 2, 2], False),
    ]
    for a, b, expected in tests:
        results = (are_equal_sorting(a, b), are_equal_hashmap(a, b), are_equal_counter(a, b))
        assert all(r == expected for r in results), (a, b, results)
        print(a, b, "->", int(expected))
    print("All tests passed")

C++ implementation

The C++ version follows the same two approaches. Note that the sorting function takes its vectors by value so the caller’s arrays are left untouched, and the hash-map version uses unordered_map for average O(1) operations.

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

// Approach 2: O(N log N). Takes copies so the inputs are not mutated.
bool areEqualSorting(vector<int> a, vector<int> b) {
    if (a.size() != b.size()) return false;
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    return a == b;   // element-wise comparison, O(N)
}

// Approach 3: O(N) average time, O(N) space.
bool areEqualHashMap(const vector<int>& a, const vector<int>& b) {
    if (a.size() != b.size()) return false;
    unordered_map<int, int> freq;
    freq.reserve(a.size() * 2);          // avoid rehashing
    for (int x : a) freq[x]++;
    for (int y : b) {
        auto it = freq.find(y);
        if (it == freq.end() || it->second == 0) return false;
        it->second--;
    }
    return true;
}

int main() {
    vector<pair<vector<int>, vector<int>>> tests = {
        {{6, 1, 7, 4, 9}, {1, 4, 7, 9, 6}},   // 1
        {{17, 12, 51},    {21, 14, 5}},       // 0
        {{1, 2, 2, 3},    {1, 2, 3, 3}},      // 0
        {{},              {}},                // 1
    };
    for (auto& [a, b] : tests) {
        cout << areEqualSorting(a, b) << " " << areEqualHashMap(a, b) << '\n';
    }
    return 0;
}

Compile with g++ -std=c++17 -O2 equal_arrays.cpp && ./a.out; both columns should print 1 1, 0 0, 0 0, 1 1.

Edge cases and common mistakes

1. Forgetting the length check. With A = {1, 2} and B = {1, 2, 2}, a hash-map loop that only decrements can falsely return true if you stop early. Compare lengths first.
2. Using a set instead of a map. set(A) == set(B) ignores duplicates and wrongly returns true for Example 3. The problem is about multisets.
3. Comparing sums or XORs. {1, 4} and {2, 3} have the same sum; XOR tricks fail similarly. These are not valid equality tests.
4. Sorting the caller’s arrays in place. Fine in a contest, dangerous in production code. Copy first or document the side effect.
5. Declaring vector B2 without a type. A classic typo in C++ (vector<int> is required) that will not compile — read your error messages.
6. Worst-case hash collisions. unordered_map can degrade to O(N) per operation with adversarial inputs. In competitive programming, a custom hash or the sorting approach avoids this.

Follow-up questions interviewers ask

• “What if the values are limited to 0–1000?” Use a plain counting array of size 1001 instead of a hash map — O(N + K) time, tiny constant factor.
• “What if the arrays are huge and do not fit in memory?” External sort both, then stream-compare; or hash-partition both arrays into buckets and compare bucket by bucket.
• “Can you do it in O(1) extra space without sorting?” Not in general for arbitrary values; that is why the trade-off between sorting and hashing matters.
• “What about strings or objects?” The hash-map approach works unchanged as long as the type is hashable; for objects, define a proper hash and equality.

Once this is comfortable, try the related array problems finding the second largest element in an array and the missing number in an array, which build on the same frequency and single-pass ideas.

Frequently asked questions

Why is the hash-map approach O(N) if hashing can collide?

With a good hash function, insertions and lookups take constant time on average, so N operations cost O(N). The worst case is O(N) per operation, but it is rare in practice and can be mitigated with a randomised hash.

Is sorted(a) == sorted(b) acceptable in an interview?

Yes, as long as you state the complexity (O(N log N)) and can explain the O(N) alternative. Interviewers care that you know the trade-off, not that you avoid library functions.

How is this different from checking if two arrays are identical?

Identical means same elements in the same positions — a single O(N) index-by-index comparison. This problem ignores order, so you must compare as multisets using sorting or counting.

Can I use this to check if one array is a permutation of another?

Yes. “Is B a permutation of A?” is exactly the same question, and it also appears as “check if two strings are anagrams” — the same frequency-map solution applies.

Key takeaways

• The problem asks whether two arrays are equal as multisets: same elements, same counts, any order.
• Brute force is O(N²); sorting gives O(N log N); a frequency hash map gives O(N) time with O(N) space.
• Always check lengths first, and never use a set — duplicates must match.
• The same pattern solves anagram checks, permutation checks and many frequency-counting interview questions.

Want to practise problems like this with mock interviews, DSA mentorship and feedback on your code? Join the Interview Preparation program at Techknowledgehub. For free walkthroughs of coding questions, subscribe to our YouTube channel.