Check if two arrays are equal or not

Difficulty: Easy, Asked-in: Microsoft, Amazon, Goldman Sachs

Key takeaway: An excellent problem to learn problem-solving using a hash table.

Let’s understand the problem!

Given two integer arrays X[] and Y[], write a program to check if both arrays are equal or not.

• Two arrays are equal if they have the same elements in any order. If there are repeated elements, then counts of repeated elements must be same in both arrays.
• Assume that elements in both arrays are non-negative.
• The size of both arrays may not be the same.

Examples

Input: X[] = [1, 2, 8], Y[] = [2, 1, 8], Output: Yes

Input: X[] = [0, 2, 5, 1, 2, 23], Y[] = [2, 0, 1, 23, 5, 2], Output: Yes

Input: X[] = [2, 5, 1, 2], Y[] = [2, 0, 1, 2], Output: No

Discussed solution approaches

• Brute force approach  using sorting
• Efficient approach  using Hash Table

Brute force approach  using sorting

The basic idea would be to arrange both arrays in either increasing or decreasing order and check elements at each position would be the same or not.

Solution steps

• We check the length of both arrays. If they are not the same, return false.
• We sort both arrays using some efficient O(nlogn) sorting algorithm.
• Now we run a loop and compare elements at each index of both arrays. Return false if any element doesn’t match. Otherwise, by the end of the loop, return true.

Solution code C++

bool equalArray(int X[], int Y[], int m, int n)
{
    if (m != n)
        return false;
    sort(X, X + m);
    sort(Y, Y + n);
    for (int i = 0; i < m; i = i + 1)
    {
        if (X[i] != Y[i])
            return false;
    }
    return true;
}

Solution code Python

def equalArray(X, Y, m, n):
    if m != n:
        return False
    X.sort()
    Y.sort()
    for i in range(m):
        if X[i] != Y[i]:
            return False
    return True

Time and space complexity analysis

• If the size of both arrays is not equal (m != n) then we are doing only one comparison. So time complexity = O(1)
• If the size of both arrays is equal (m == n), then time complexity = Time complexity of sorting X[] + Time complexity of sorting Y[] + Time complexity of comparing both arrays = O(mlogm) + O(nlogn) + O(m) = O(mlogm + nlogn) = O(nlogn)
• If we use an in-place sorting algorithm like heap sort, space complexity = O(1).

Efficient approach  using Hash Table

Solution idea

Now the critical question is: how we optimize the time complexity further? One idea would be that both arrays are sorted in the previous approach, so we can think to use binary search instead of linear search for comparing both arrays. But here, time complexity would still be dominated by the sorting algorithms. So, can we solve this problem without using sorting? Can we use a hash table to improve the time complexity? Let's think!

The idea is: if elements in both arrays are equal and their frequency count is also the same then both arrays must be equal. So we need an efficient mechanism to store and search values with their frequency count. That's why the hash table is a perfect choice to solve this problem because it performs insert and search operations efficiently in O(1) average.

Solution steps

• We create a hash table H of size m, where each element of array X[] would work as a key and frequency count as their value.
• We scan the array X[] and store the frequency count of each element in the hash table. In other words, whenever we find a X[i] repeating in the hash table, we increase its frequency count by 1.
• Now we scan the array Y[] and search each element Y[i] in the hash table. If it is not present, then this is the scenario of the first mismatch, and both arrays are not equal. So we return false.
• If the value Y[i] is present in the hash table, then we decrement its corresponding frequency count by 1. If the frequency count of any element in the hash table becomes 0, it means element Y[i] appears more times in Y[] than it appears in X[]. So both arrays are not equal, and we return false.
• We continue the above process for all elements in array Y[]. If we reach the end of the loop, both arrays are equal, and we return true.

Solution pseudocode

bool equalArray(int X[], int Y[], int m, int n)
{
    if (m != n)
        return false
    Hash Table H
    for (int i = 0; i < m; i = i + 1)
        H[X[i]] = H[X[i]] + 1
    for (int i = 0; i < m; i = i + 1) 
    {
        if (H.search(Y[i]) == false)
            return false 
        if (H[Y[i]] == 0)
            return false
        H[Y[i]] =  H[Y[i]] - 1
    }
    return true
}

Solution code C++

bool equalArray(int X[], int Y[], int m, int n)
{
    if (m != n)
        return false;
    unordered_map<int, int> H;
    
    for (int i = 0; i < m; i = i + 1)
        H[X[i]] = H[X[i]] + 1;
        
    for (int i = 0; i < m; i = i + 1)
    {
        if (H.find(Y[i]) == H.end())
            return false;
        if (H[Y[i]] == 0)
            return false;
        H[Y[i]] = H[Y[i]] - 1;
    }
    return true;
}

Solution code Python

def equalArray(X, Y, m, n):
    if m != n:
        return False
    H = defaultdict(int)
    
    for i in range(m):
        H[X[i]] = H[X[i]] + 1
        
    for i in range(m):
        if Y[i] not in H:
            return False
        if H[Y[i]] == 0:
            return False
        H[Y[i]] = H[Y[i]] - 1
        
    return True

Time and space complexity analysis

• The time complexity of insert and search operations in the hash table = O(1) average.
• We are running two separate loops and performing O(1) operations at each iteration of both loops. So time complexity = m*O(1) + m *O(1) = O(m) on average.
• Space complexity = O(m), for storing the hash table of size m.

Critical ideas to think!

• Can we solve it using a binary search tree?
• How can we modify the hash table approach to solve the problem for the negative elements also? Is there any modification required or not?
• Can we solve this problem in O(n) time complexity and constant space for specific kinds of inputs? Explore an example of such kinds of input.
• If all elements of both arrays are positive, can we solve the problem by checking the sum and product of elements for both arrays?
• Suppose elements in both arrays are unique. Can we solve this problem using a bitwise XOR operation? Here we have presented a basic sample of steps. Is this approach correct? Think!
• We take XOR of all elements in array X[] and store this value in the variable xorX.
• We take XOR of all elements in array Y[] and store this value in the variable xorY.
• Now we take the overall XOR of both values stored on xorX and corY. If the value of this combined XOR is 0, both arrays are equal, and we return true. Otherwise, both arrays are not equal, and we return false.

Pseudocode

bool equalArray(int X[], int Y[], int m, int n)
{
    if (n != m)
        return false
        
    int xorX = X[0]
    int xorY = Y[0]

    for (int i = 1; i < m; i = i + 1)
        xorX = xorX ^ X[i]
 
    for (int i = 1; i < n; i = i + 1)
        xorY = xorY ^ Y[i]
        
    if ((xorX ^ xorY) == 0)
        return true
        
    return false
}

Suggested coding questions to practice

• n Repeated element in 2n size array
• Check for pair in an array with a given sum
• Find the majority element in an array
• Check whether an array is a subset of another array
• Find the most frequent element in an array
• Longest consecutive sequence
• First missing positive

Enjoy learning, Enjoy problem-solving!