Check Equal Arrays

Problem

Given two arrays A and B of equal size N, the task is to find if given arrays are equal or not. Two arrays are said to be equal if both of them contain same set of elements, arrangements (or permutation) of elements may be different though.

Note: If there are repetitions, then counts of repeated elements must also be same for two array to be equal.

Examples:

Example 1:

Input:
N = 5
A[] = {1,2,5,4,0}
B[] = {2,4,5,0,1}
Output: 1
Explanation: Both the array can be rearranged to {0,1,2,4,5}

Example 2:

Input:
N = 3
A[] = {1,2,5}
B[] = {2,4,15}
Output: 0
Explanation: A[] and B[] have only one common value.

Your Task:

Complete check() function which takes both the given array and their size as function arguments and returns true if the arrays are equal else returns false. The 0 and 1 printing is done by the driver code.

• Expected Time Complexity: $O(N)$
• Expected Auxilliary Space: $O(N)$

Constraints:

• $1<=N<=10^7$
• $1<=A[],B[]<=10^{18}$

Solution

Python

def check(self,A,B,N):
    if len(A) != len(B):
        return False
    count = {}
    for i in A:
        if i in count:
            count[i] += 1
        else:
            count[i] = 1
    for i in B:
        if i not in count or count[i] == 0:
            return False
        else:
            count[i] -= 1
    return True

Java

public static boolean check(long A[],long B[],int N) {
    if (A.length != B.length || A.length != N)
        return false;
    Map<Long, Integer> map = new HashMap<>();
    for (int i = 0; i < N; i++) {
        long key = A[i];
        map.put(key, map.getOrDefault(key, 0) + 1);
    }
    for (int i = 0; i < N; i++) {
        long key = B[i];
        if (!map.containsKey(key))
            return false;
        if (map.get(key) == 0)
            return false;
        int count = map.get(key);
        map.put(key, count - 1);
    }
    return true;
}

C++

bool check(vector<ll> A, vector<ll> B, int N) {
    if (A.size() != static_cast<size_t>(N) || B.size() != static_cast<size_t>(N))
        return false;
    unordered_map<ll, int> map;
    for (int i = 0; i < N; ++i) {
        ll key = A[i];
        map[key]++;
    }
    for (int i = 0; i < N; ++i) {
        ll key = B[i];
        if (map.find(key) == map.end())
            return false;
        if (map[key] == 0)
            return false;
        map[key]--;
    }
    return true;
}

C

bool check(long long A[], long long B[], int N) {
    long long *map = (long long *)calloc(1000001, sizeof(long long));
    for (int i = 0; i < N; ++i) {
        long long key = A[i];
        map[key]++;
    }
    for (int i = 0; i < N; ++i) {
        long long key = B[i];
        if (map[key] == 0)
            return false;
        map[key]--;
    }
    free(map); 
    return true;
}

• Time Complexity: $O(N)$
• Auxilliary Space: $O(N)$