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

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

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.

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

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

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.

- 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.

```
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;
}
```

```
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
```

- 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).

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.

- 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.

```
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
}
```

```
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;
}
```

```
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
```

- 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.

- 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.

```
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
}
```

- 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!**

☆ 16-Week Live DSA Course

☆ 10-Week Live DSA Course

Subscribe to get well designed content on data structure and algorithms, machine learning, system design, object orientd programming and math.

©2023 Code Algorithms Pvt. Ltd.

All rights reserved.