C++ Program to check if two Arrays are Equal or not

Given two arrays arr1[] and arr2[] of length N and M respectively, the task is to check if the two arrays are equal or not.

Note: Arrays are said to be equal if and only if both arrays contain the same elements and the frequencies of each element in both arrays are the same.

Examples:

Input: arr1[] = {1, 2, 3, 4, 5}, arr2[] = {5, 4, 3, 2, 1}
Output : Equal
Explanation: As both the arrays contain same elements.

Input: arr1[] = {1, 5, 2, 7, 3, 8}, arr2[] = {8, 2, 3, 5, 7, 1}
Output : Equal

Naive Approach: The basic way to solve the problem is as follows:

Apply sorting on both the arrays and then match each element of one array with the element at same index of the other array.

Follow the steps mentioned below to implement the idea.

Check if the length of both the arrays are equal or not
Then sort both the arrays, so that we can compare every equal element.
Linearaly iterate over both the arrays and check if the elements are equal or not,
If equal then print Equal and if not then print Not equal.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

bool checkArrays(int arr1[], int arr2[],

int n, int m)

{

if (n != m)

return false;

sort(arr1, arr1 + n);

sort(arr2, arr2 + m);

for (int i = 0; i < n; i++)

if (arr1[i] != arr2[i])

return false;

return true;

}

int main()

{

int arr1[] = { 1, 2, 3, 4, 5 };

int arr2[] = { 5, 4, 3, 2, 1 };

int N = sizeof(arr1) / sizeof(int);

int M = sizeof(arr2) / sizeof(int);

if (checkArrays(arr1, arr2, N, M))

cout << "Equal";

else

cout << "Not Equal";

return 0;

}

Output

Equal

Time Complexity: O(N * logN)
Auxiliary Space: O(1)

Efficient Approach: The problem can be solved efficiently using Hashing (unordered_map),

Use hashing to count the frequency of each element of both arrays. Then traverse through the hashtables of the arrays and match the frequencies of the elements.

Follow the below mentioned steps to solve the problem:

Check if the length of both the arrays are equal or not
Create an unordered map and store all elements and frequency of elements of arr1[] in the map.
Traverse over arr2[] and check if count of each and every element in arr2[] matches with the count in arr1[]. This can be done by decrementing the frequency while traversing in arr2[].

Below is the implementation of the above approach: