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 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!
There are four critical importance to learn data structures and algorithms: 1) An algorithm is a technology 2) It is at the core of library functions and several APIs 3) For cracking the coding interview 4) Algorithms are beautiful! This blog answer one of the critical questions: how do we develop a long-term motivation to learn data structures and algorithms?
Given an array X[] of n integers, return true if and only if it is a valid mountain array. The array X[] is a mountain array if and only if n >= 3 and there exists some i with 0 < i < n - 1 such that: X[0] < X[1] <...X[i-1] < X[i] and X[i] > X[i+1] > ...> X[n - 1]. In other words, we call the array mountain array when the array is strictly increasing and then strictly decreasing.
Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops and math. enjoy learning!