Check if two arrays are equal or not
Last Updated :
20 Jun, 2024
Given two arrays, arr1 and arr2 of equal length N, the task is to determine if the given arrays are equal or not. Two arrays are considered equal if:
- Both arrays contain the same set of elements.
- The arrangements (or permutations) of elements may be different.
- If there are repeated elements, the counts of each element must be the same in both arrays.
Examples:
Input: arr1[] = {1, 2, 5, 4, 0}, arr2[] = {2, 4, 5, 0, 1}
Output: Yes
Input: arr1[] = {1, 2, 5, 4, 0, 2, 1}, arr2[] = {2, 4, 5, 0, 1, 1, 2}
Output: Yes
Input: arr1[] = {1, 7, 1}, arr2[] = {7, 7, 1}
Output: No
Approaches to check if two arrays are equal or not
[Naive Approach] Using Sorting – O(N*log(N)) time and O(1) auxiliary Space
The basic idea is to sort the both given arrays and idea behind sorting is that once both arrays are sorted, they will be identical if and only if they contain the same elements in the same quantities. After sorting, we compare the arrays element by element. If any pair of corresponding elements in the sorted arrays differ, we return false (i.e indicating the arrays are not equal). If all elements match, we return true.
Code Implementation:
C++
// C++ program to find given two array
// are equal or not
#include <bits/stdc++.h>
using namespace std;
// Returns true if arr1[0..n-1] and arr2[0..m-1]
// contain same elements.
bool areEqual(int arr1[], int arr2[], int N, int M)
{
// If lengths of array are not equal means
// array are not equal
if (N != M)
return false;
// Sort both arrays
sort(arr1, arr1 + N);
sort(arr2, arr2 + M);
// Linearly compare elements
for (int i = 0; i < N; i++)
if (arr1[i] != arr2[i])
return false;
// If all elements were same.
return true;
}
// Driver's Code
int main()
{
int arr1[] = { 3, 5, 2, 5, 2 };
int arr2[] = { 2, 3, 5, 5, 2 };
int N = sizeof(arr1) / sizeof(int);
int M = sizeof(arr2) / sizeof(int);
// Function call
if (areEqual(arr1, arr2, N, M))
cout << "Yes";
else
cout << "No";
return 0;
}
// Java program to find given two array
// are equal or not
import java.io.*;
import java.util.*;
class GFG {
// Returns true if arr1[0..n-1] and
// arr2[0..m-1] contain same elements.
public static boolean areEqual(int arr1[], int arr2[])
{
int N = arr1.length;
int M = arr2.length;
// If lengths of array are not equal means
// array are not equal
if (N != M)
return false;
// Sort both arrays
Arrays.sort(arr1);
Arrays.sort(arr2);
// Linearly compare elements
for (int i = 0; i < N; i++)
if (arr1[i] != arr2[i])
return false;
// If all elements were same.
return true;
}
// Driver code
public static void main(String[] args)
{
int arr1[] = { 3, 5, 2, 5, 2 };
int arr2[] = { 2, 3, 5, 5, 2 };
// Function call
if (areEqual(arr1, arr2))
System.out.println("Yes");
else
System.out.println("No");
}
}
# Python3 program to find given
# two array are equal or not
# Returns true if arr1[0..n-1] and
# arr2[0..m-1] contain same elements.
def areEqual(arr1, arr2, N, M):
# If lengths of array are not
# equal means array are not equal
if (N != M):
return False
# Sort both arrays
arr1.sort()
arr2.sort()
# Linearly compare elements
for i in range(0, N):
if (arr1[i] != arr2[i]):
return False
# If all elements were same.
return True
# Driver Code
if __name__ == "__main__":
arr1 = [3, 5, 2, 5, 2]
arr2 = [2, 3, 5, 5, 2]
n = len(arr1)
m = len(arr2)
if (areEqual(arr1, arr2, n, m)):
print("Yes")
else:
print("No")
// C# program for the above approach
using System;
class GFG {
// Returns true if arr1[0..n-1] and
// arr2[0..m-1] contain same elements.
public static bool areEqual(int[] arr1, int[] arr2)
{
int N = arr1.Length;
int M = arr2.Length;
// If lengths of array are not
// equal means array are not equal
if (N != M)
return false;
// Sort both arrays
Array.Sort(arr1);
Array.Sort(arr2);
// Linearly compare elements
for (int i = 0; i < N; i++)
if (arr1[i] != arr2[i])
return false;
// If all elements were same.
return true;
}
// Driver's code
public static void Main()
{
int[] arr1 = { 3, 5, 2, 5, 2 };
int[] arr2 = { 2, 3, 5, 5, 2 };
// Function call
if (areEqual(arr1, arr2))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by anuj_67.
<script>
// JavaScript program for the above approach
// Returns true if arr1[0..n-1] and arr2[0..m-1]
// contain same elements.
function areEqual(arr1, arr2)
{
let N = arr1.length;
let M = arr2.length;
// If lengths of array are not equal means
// array are not equal
if (N != M)
return false;
// Sort both arrays
arr1.sort();
arr2.sort();
// Linearly compare elements
for (let i = 0; i < N; i++)
if (arr1[i] != arr2[i])
return false;
// If all elements were same.
return true;
}
// Driver Code
let arr1 = [3, 5, 2, 5, 2];
let arr2 = [2, 3, 5, 5, 2];
if (areEqual(arr1, arr2))
document.write("Yes");
else
document.write("No");
</script>
<?php
// PHP program to find given
// two array are equal or not
// Returns true if arr1[0..n-1]
// and arr2[0..m-1] contain same elements.
function areEqual( $arr1, $arr2, $N, $M)
{
// If lengths of array
// are not equal means
// array are not equal
if ($N != $M)
return false;
// Sort both arrays
sort($arr1);
sort($arr2);
// Linearly compare elements
for ( $i = 0; $i < $N; $i++)
if ($arr1[$i] != $arr2[$i])
return false;
// If all elements were same.
return true;
}
// Driver Code
$arr1 = array(3, 5, 2, 5, 2);
$arr2 = array(2, 3, 5, 5, 2);
$N = count($arr1);
$M = count($arr2);
// Function call
if (areEqual($arr1, $arr2, $N, $M))
echo "Yes";
else
echo "No";
?>
Time Complexity: O(N*log(N))
Auxiliary Space: O(1)
[Expected Approach] Using Hashing – O(N) time and O(N) auxiliary space
The hashing approach is more efficient approach for this problem. The use of a hash map (or dictionary) is to count the occurrences of each element in one array and then verifying these counts against the second array.
Code Implementation:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Returns true if arr1[0..N-1] and arr2[0..M-1]
// contain same elements.
bool areEqual(int arr1[], int arr2[], int N, int M)
{
// If lengths of arrays are not equal
if (N != M)
return false;
// Store arr1[] elements and their counts in
// hash map
unordered_map<int, int> mp;
for (int i = 0; i < N; i++)
mp[arr1[i]]++;
// Traverse arr2[] elements and check if all
// elements of arr2[] are present same number
// of times or not.
for (int i = 0; i < N; i++) {
// If there is an element in arr2[], but
// not in arr1[]
if (mp.find(arr2[i]) == mp.end())
return false;
// If an element of arr2[] appears more
// times than it appears in arr1[]
if (mp[arr2[i]] == 0)
return false;
// decrease the count of arr2 elements in the
// unordered map
mp[arr2[i]]--;
}
return true;
}
// Driver's Code
int main()
{
int arr1[] = { 3, 5, 2, 5, 2 };
int arr2[] = { 2, 3, 5, 5, 2 };
int N = sizeof(arr1) / sizeof(int);
int M = sizeof(arr2) / sizeof(int);
// Function call
if (areEqual(arr1, arr2, N, M))
cout << "Yes";
else
cout << "No";
return 0;
}
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Returns true if arr1[0..N-1] and arr2[0..M-1]
// contain same elements.
public static boolean areEqual(int arr1[], int arr2[])
{
int N = arr1.length;
int M = arr2.length;
// If lengths of arrays are not equal
if (N != M)
return false;
// Store arr1[] elements and their counts in
// hash map
Map<Integer, Integer> map
= new HashMap<Integer, Integer>();
int count = 0;
for (int i = 0; i < N; i++) {
if (map.get(arr1[i]) == null)
map.put(arr1[i], 1);
else {
count = map.get(arr1[i]);
count++;
map.put(arr1[i], count);
}
}
// Traverse arr2[] elements and check if all
// elements of arr2[] are present same number
// of times or not.
for (int i = 0; i < N; i++) {
// If there is an element in arr2[], but
// not in arr1[]
if (!map.containsKey(arr2[i]))
return false;
// If an element of arr2[] appears more
// times than it appears in arr1[]
if (map.get(arr2[i]) == 0)
return false;
count = map.get(arr2[i]);
--count;
map.put(arr2[i], count);
}
return true;
}
// Driver's code
public static void main(String[] args)
{
int arr1[] = { 3, 5, 2, 5, 2 };
int arr2[] = { 2, 3, 5, 5, 2 };
// Function call
if (areEqual(arr1, arr2))
System.out.println("Yes");
else
System.out.println("No");
}
}
# Python3 program for the above approach
# Returns true if arr1[0..N-1] and
# arr2[0..M-1] contain same elements.
def is_arr_equal(arr1, arr2):
# Check if the length of arrays are
# equal or not: A Easy Logic Check
if len(arr1) != len(arr2):
return False
# Create a dict named count to
# store counts of each element
count = {}
# Store the elements of arr1
# and their counts in the dictionary
for i in arr1:
if i in count:
# Element already in dict, simply increment its count
count[i] += 1
else:
# Element found for first time, initialize it with value 1.
count[i] = 1
# Traverse through arr2 and compare
# the elements and its count with
# the elements of arr1
for i in arr2:
# Return false if the element
# is not in count or if any element
# appears more no. of times than in arr1
if i not in count or count[i] == 0:
return False
else:
# If element is found, decrement
# its value in the dictionary
count[i] -= 1
# Return true if both arr1 and
# arr2 are equal
return True
# Driver Code
if __name__ == "__main__":
arr1 = [3, 5, 2, 5, 2]
arr2 = [2, 3, 5, 5, 2]
if is_arr_equal(arr1, arr2):
print("Yes")
else:
print("No")
// C# program to find given two array
// are equal or not using hashing technique
using System;
using System.Collections.Generic;
class GFG {
// Returns true if arr1[0..N-1] and arr2[0..M-1]
// contain same elements.
public static bool areEqual(int[] arr1, int[] arr2)
{
int N = arr1.Length;
int M = arr2.Length;
// If lengths of arrays are not equal
if (N != M)
return false;
// Store arr1[] elements and their counts in
// hash map
Dictionary<int, int> map
= new Dictionary<int, int>();
int count = 0;
for (int i = 0; i < N; i++) {
if (!map.ContainsKey(arr1[i]))
map.Add(arr1[i], 1);
else {
count = map[arr1[i]];
count++;
map.Remove(arr1[i]);
map.Add(arr1[i], count);
}
}
// Traverse arr2[] elements and check if all
// elements of arr2[] are present same number
// of times or not.
for (int i = 0; i < N; i++) {
// If there is an element in arr2[], but
// not in arr1[]
if (!map.ContainsKey(arr2[i]))
return false;
// If an element of arr2[] appears more
// times than it appears in arr1[]
if (map[arr2[i]] == 0)
return false;
count = map[arr2[i]];
--count;
if (!map.ContainsKey(arr2[i]))
map.Add(arr2[i], count);
}
return true;
}
// Driver's code
public static void Main(String[] args)
{
int[] arr1 = { 3, 5, 2, 5, 2 };
int[] arr2 = { 2, 3, 5, 5, 2 };
// Function call
if (areEqual(arr1, arr2))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
/* This code contributed by PrinciRaj1992 */
<script>
// Javascript program to find given two array
// are equal or not using hashing technique
// Returns true if arr1[0..N-1] and arr2[0..M-1]
// contain same elements.
function areEqual(arr1, arr2)
{
let N = arr1.length;
let M = arr2.length;
// If lengths of arrays are not equal
if (N != M)
return false;
// Store arr1[] elements and their counts in
// hash map
let map
= new Map();
let count = 0;
for (let i = 0; i < N; i++) {
if (map.get(arr1[i]) == null)
map.set(arr1[i], 1);
else {
count = map.get(arr1[i]);
count++;
map.set(arr1[i], count);
}
}
// Traverse arr2[] elements and check if all
// elements of arr2[] are present same number
// of times or not.
for (let i = 0; i < N; i++) {
// If there is an element in arr2[], but
// not in arr1[]
if (!map.has(arr2[i]))
return false;
// If an element of arr2[] appears more
// times than it appears in arr1[]
if (map.get(arr2[i]) == 0)
return false;
count = map.get(arr2[i]);
--count;
map.set(arr2[i], count);
}
return true;
}
// Driver code
let arr1 = [3, 5, 2, 5, 2];
let arr2 = [2, 3, 5, 5, 2];
// Function call
if (areEqual(arr1, arr2))
document.write("Yes");
else
document.write("No");
</script>
Time Complexity: O(N)
Auxiliary Space: O(N)
Please Login to comment...