Introduction
In this article, we will discuss the problem to check if two arrays are equal or not and briefly discuss the approach to be used and its time and space complexity.
Before discussing the problem statement to check if two arrays are equal or not, let us first discuss what an array means.
Array: It is a linear data structure consisting of a collection of values called elements of an array, stored in a contiguous memory location and can be accessed using array indexes.
In this article, we will look at how to solve the problem statement to check if two arrays are equal or not, alongside an example.
Idea Behind the Problem
The task is to determine whether or not two arrays of identical lengths are equal. When two arrays have the same set of items, they are said to be equal; the arrangements (or permutations) of the elements, however, may differ.
Remember that the count of repeated elements must match if there are repetitions for two arrays to be equal.
Brute Force Method
The basic concept is to arrange the elements in both arrays in either increasing or decreasing order and then determine whether or not they are the same at each place.
Approach
-
We measure the length of both arrays. The function will return false if they aren't the same.
-
We will then sort both the arrays using an efficient O(N log N) sorting algorithm.
-
Now, we will run a loop across both arrays, comparing values at each index. If any element doesn't match, it will return false. Or else return true at the ending of the loop.
Brute Force Pseudocode
/*
Brute force pseudocode to check if two arrays are equal or not.
*/
bool ifArrayEqual(int firstArray[], int secondArray[], int a, int b)
{
if (a != b)
return false
heapSort(firstArray, a)
heapSort(secondArray, b)
for (int i = 0; i < a; i = i+1)
{
if (firstArray[i] != secondArray[i])
return false
}
return true
}Brute Force Complexities
-
We only perform one comparison if the sizes of the two arrays are not equal, i.e., a != b, then time complexity = O(1).
-
If the size of both arrays is identical, i.e., a == b, then the time complexity
= Time complexity of sorting firstArray[] + Time complexity of sorting secondArray[] + Time complexity of comparing both arrays
= O(aloga) + O(blogb) + O(a)
= O(aloga + blogb), i.e., O(NlogN + NlogN)
= O(NlogN)
- Space complexity = O(1) if we employ an in-place sorting technique like heap sort.
Hashing Method
To reduce the complexity of the problem, we will use an unordered map, which is implemented using a hash table in hashing method. The concept is that both arrays must have equal elements if their frequency counts are also equal for all members in both arrays. Therefore, we require an efficient method for storing and searching variables based on their frequency count.
Since it efficiently completes insert and search operations in O(1) on average, the hash table is a perfect solution to this issue.
Approach
-
We will create a hash table ‘ht’ of size ‘a’. Each element of the array ‘firstArray[]’ serves as a key and the frequency count serves as its value in a hash table ‘ht’ that we generated.
-
The frequency count of each element is recorded in the hash table as we scan the array ‘firstArray[]’. In other words, we add 1 to the frequency count of any ‘firstArray[i]’ that repeats in the hash table.
-
Now, we search each ‘secondArray[i]’ element in the hash table by scanning the array ‘secondArray[]’. If it is absent, the first mismatch will occur, and both arrays will not be equal. Thus, we return false.
-
We decrease the specific frequency count of the value ‘secondArray[i]’ by 1 if it appears in the hash table. In the hash table, if any element's frequency count reaches 0, it signifies that element ‘secondArray[i]’ appears more frequently in ‘secondArray[]’ than it does in ‘firstArray[]’. Thus, we return false because the two arrays are not identical.
-
For each component in array ‘secondArray[]’, the same procedure is repeated. Both arrays are equal if we reach the end of the loop; therefore, we return true.
Let us take an example of two arrays as input each of size = 3 for ‘firstArray’ and ‘secondArray’.
[Note that if the sizes of both arrays are not equal then the function will return with boolean value ‘false’. Hence, the output will be printed as ‘False, the two arrays are not equal.’]
Now, when the size of the arrays is equal, the function will compare the two arrays in the following way:
firstArray[]={1, 8, 2}
secondArray[]={2, 1, 8}
In the beginning, we will store the ‘firstArray’ elements in the hashtable along with their frequencies.
Now we will check the ‘secondArray’ elements with the ‘firstArray’ elements in the hashtable.
In the loop, for i=0 and i<3:
For i=1 and i<3:
For i=2 and i<3:
Now, in the end, since no elements are present in the ‘secondArray’ to check the occurrences as ‘i’ cannot be equal to or more than 3, the boolean function will return ‘true’.
Hence, the output will be: True, the two arrays are equal.
Other cases of the boolean function ‘ifArrayEqual’ returning ‘false’ occurs when the frequencies mismatch between the arrays.
Hashing Pseudocode
/*
Hashing pseudocode to check if two arrays are equal or not.
*/
bool ifArrayEqual(int firstArray[], int secondArray[], int a, int b)
{
if (a != b)
return false
unordered_map<int, int> ht
for (int i = 0; i < a; i = i+1)
{
ht[firstArray[i]] = ht[secondArray[i]] + 1
}
for (int i = 0; i < a; i = i + 1)
{
if (ht.find(secondArray[i]) == ht.end())
return false
if (ht[secondArray[i]] == 0)
return false
ht[secondArray[i]] = ht[secondArray[i]] - 1
}
return true
}Hashing Complexities
-
The hash table's insert and search operations take an average of O(1) time to complete.
-
Each iteration of our two independent loops involves performing O(1) operations. So, on average, time complexity
= a*O(1) + a*O(1)
= O(a), i.e., O(N).
- For storing a hash table of size ‘N’, the space complexity is O(N).
85+ registered