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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions