Home » Data Structure » Hashing Coding Problems

Check if two arrays are similar or not using hashing

Here, we are going to discuss how to check whether two arrays are exactly similar or not using has table?
Submitted by Radib Kar, on July 02, 2020

Prerequisite: Hashing data structure

Problem statement:

Check whether two arrays are similar or not using the hash table. The arrays are of the same size.

Example

arr1= [1, 2, 1, 3, 2, 1]
arr2= [2, 2, 3, 1, 1, 1]

Solution

There are several ways to solving this problem and one is by sorting both of the array. Then we can check elements one by one and if the two arrays are similar, it has to match for every single element. So, after sorting, a[i] must be b[i] for each i. But the method we will discuss is hashing which computes more easily.

The approach is to create two separate hash tables for each array. If the hash tables are exactly same then we can say that the arrays are exactly same.

So how can we create the hash tables and what will be the hash function?

Okay, so here each element is our key and the hash table has size of the range of the array. So, if the range of the array is [0,99] then the hash table size would be 100.
What will be our hash function and how would we map the keys to the corresponding location in the hash table?

The hash function h(x)=x here but instead of storing the key itself using linear probing we will keep the frequency (this is same as the number of collisions) only as it does not make any sense to use linear probing as each unique key will have a unique location.

So, for example, if we have three 2s as our key, the hash table will store the count (frequency) at location 2.

So, using the above hash function, we will create two separate hash tables for two arrays (The hash function will remain the same for both)

So the algorithm will be,

Step 1:

Create the hash table like below:
Initially hash tables are empty (Hash1 & Hash2)

For each key in input array arr1:
Hash1[key]++

For each key in input array arr2:
Hash2[key]++

Step 2:

Compare each location of the hash table
If all locations have the same value (same frequency for each unique key) 
then the two arrays are the same otherwise not.

Dry run with the example:

arr1= [1, 2, 1, 3, 2, 1]
arr2= [2, 2, 3, 1, 1, 1]

After creating the hash table as step1 we will have

Hash1:
Index	Value
1	3
2	2
3	1
  
Hash2:
Index	Value
1	3
2	2
3	1

So, 
both hash1 and hash 2 is exactly 
the same and thus the arrays are same too.

Another example where arrays are not exactly same,
arr1= [1, 2, 1, 3, 2, 3]
arr2= [2, 2, 3, 1, 1, 1]

After creating the hash table as step1 we will have
Hash1:
Index	Value
1	2
2	2
3	2
  
Hash2:
Index	Value
1	3
2	2
3	1

Since location 1 has different values for hash1 and hash2 
we can conclude the arrays are not the same.
So, what we actually did using hashing is to check 
whether all the unique elements in the two arrays are exactly 
the same or not and if the same then their 
frequencies are the same or not.

C++ Implementation

//C++ program to check if two arrays 
//are equal or not

#include <bits/stdc++.h>
using namespace std;

bool similar_array(vector<int> arr1, vector<int> arr2)
{
    //create teo different hash table where for each key 
    //the hash function is h(arr[i])=arr[i]
    //we will use stl map as hash table and 
    //will keep frequency stored
    //so say two keys arr[0] and arr[5] are mapping to 
    //the same location, then the location will have value 2
    //instead of the keys itself
    //if two hash tables are exactly same then 
    //we can say that our arrays are similar
    map<int, int> hash1;
    map<int, int> hash2;

    //for each number
    for (int i = 0, j = 0; i < arr1.size(); i++, j++) {
        hash1[arr1[i]]++;
        hash2[arr2[i]]++;
    }

    //now check whether hash tables are exactly same or not
    for (auto it = hash1.begin(), ij = hash2.begin(); it != hash1.end() && ij != hash2.end(); it++, ij++) {
        if (it->first != ij->first || it->second != ij->second)
            return false;
    }

    //so ans will be updated maxdiff
    return true;
}

int main()
{
    int n, m;
 
    cout << "Enter number of elements for array1 & array2\n";
    cin >> n;

    //arrays having equal sum
    vector<int> arr1(n, 0);
    vector<int> arr2(n, 0);
    cout << "Input the array elements\n";

    for (int i = 0; i < n; i++) {
        cin >> arr1[i];
        cin >> arr2[i];
    }
 
    if (similar_array(arr1, arr2))
        cout << "The arrys are equal";
    else
        cout << "The arrys are not equal";

    return 0;        
}

Output:

Enter number of elements for array1 & array2
6
Input the array elements
1 2 1 3 2 1
2 2 3 1 1 1
The arrys are equal