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