Sorting: Check if two arrays are equal or not

Problem Statement:

You are given 2 arrays, you need to check if the array are same or not

Example:

Input:

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

Output:

True

Solution 1: Sorting

Sort both the arrays and compare the elements one by one.

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

Solution 2: Hashing

Add the contents of one array into hashmap and verify these counts against the second array.

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

Code Solution

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

bool solutution_1(vector<int>& a, vector<int>& b) 
{
    
    int n = a.size();
    int m = b.size();

    if (n != m) 
    	return false;

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    for (int i = 0; i < n; i++)
        if (a[i] != b[i])
            return false;

    return true;
}

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

  	int n = a.size();
  	int m = b.size();

    if (n != m)
        return false;

    unordered_map<int, int> mp;
    
    for (int i = 0; i < n; i++)
        mp[a[i]]++;

    for (int i = 0; i < n; 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, 5 };
    vector<int> b = { 5, 4, 3, 2, 1 };

    if (solutution_1(a, b))
        cout << "true";
    else
        cout << "false";
    return 0;
}

Output

true