Difficulty: Easy, Askedin: Microsoft, Amazon, Goldman Sachs
Key takeaway: An excellent problem to learn problemsolving 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 the same for both arrays.
 Assume that elements in both arrays are nonnegative.
 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
 A brute force approach using sorting
 An efficient approach using a 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 effcient 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 Pseudocode
bool equalArray(int X[], int Y[], int m, int n)
{
if (m != n)
return false
heapSort(X, m)
heapSort(Y, n)
for (int i = 0; i < m; i = i + 1)
{
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 inplace sorting algorithm like heap sort, space complexity = O(1).
An efficient approach using a 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 effcient 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
}
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.
Solution 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
Enjoy learning, Enjoy problemsolving!