Difficulty: Easy, Asked-in: Microsoft, Amazon, Goldman Sachs
Key takeaway: A good problem to learn problem-solving using a hash table.
Given two integer arrays X[] and Y[], write a program to check if the arrays are equal or not.
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
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
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
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
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
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
}
Enjoy learning, Enjoy problem-solving!
Get well-designed application and interview centirc content on ds-algorithms, machine learning, system design and oops. Content will be delivered weekly.