Hashing: Given 2 arrays, check if they are equal or not

Problem Statement:

You are given 2 arrays, you need to check if 2 arrays are equal if they satisfy below 2 conditions:

1. Both array contains same set of elements.

2. Permutation can be different.

3. Representative element count should be same

Example:

Input:

a = [1, 2, 3, 4, 4, 5, 6]
b = [6, 5, 4, 4, 3, 2, 1]

Output: True

Solution 1: Brute force approach

Sort both of the arrays.

Compare both the element one by one if they are same or not

Time Complexity: O(n*logn)
Space Complexity: O(1)

Solution 2: Hashing approach

Use hash map to count the occurrence of each element in one array.

Traverse the second array and then check if the counts are same.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <unordered_map>
using namespace std;


bool solution_1 (vector<int> a, vector<int> b) {

    if (a.size() != b.size()) 
    	return false;

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    
    for (int i = 0; i < a.size(); i++)
        if (a[i] != b[i])
            return false;
    return true;
}

bool solution_2 (vector<int>& a, vector<int>& b) {

    if (a.size() != b.size()) 
    	return false;

    unordered_map<int, int> mp;

    for (int i = 0; i < a.size(); i++)
        mp[a[i]]++;

    for (int i = 0; i < a.size(); i++) {
        if (mp.find(b[i]) == mp.end())
            return false;

        if (mp[b[i]] == 0)
            return false;
      
        mp[b[i]]--;
    }
    return true;
}

int main() {
    vector<int> a = { 1, 2, 3, 4, 4, 5, 6 };
    vector<int> b = { 6, 5, 4, 4, 3, 2, 1 };

    if (solution_1(a, b))
        cout << "true";
    else
        cout << "false";
    cout<<endl;
    if (solution_2(a, b))
        cout << "true";
    else
        cout << "false";

    return 0;
}

Output

true
true