Given two arrays, A[] and B[], the task is to check if they are equal or not. Arrays are considered equal if any permutation of array B equates to array A.
Examples:
Input: A[] = [2, 4, 5, 7, 5, 6] and B[] = [4, 2, 5, 5, 6, 7]
Output: Yes
Explanation: All the elements in array A are present in array B and same number of times.Input: A[] = [2, 5, 8, 9, 78] and B[] = [5, 2, 7, 78, 8]
Output: No
Explanation: In array A there is a 9 and in array B there is a 7
Approach: The problem can be solved using hashmap based on the below idea:
Two arrays will be equal only if the frequency of the respective elements in both arrays are equal.
Follow the steps to solve the problem:
- If the sizes of both arrays are not equal, return NO.
- Maintain a hashmap and count the frequency of both the array elements
- If for any element the frequency is not the same, then return NO
- Otherwise, return YES
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;bool isEqual(vector<int> a, vector<int> b, int n, int m){ // If size is not same return false if (n != m) { return 0; } // Create 2 unordered maps to store // the frequency unordered_map<int, int> mp1, mp2; for (int i : a) { mp1[i]++; } for (int i : b) { mp2[i]++; } // Compare the frequency for (auto i = mp1.begin(); i != mp1.end(); i++) { // If frequency not same return false if (mp2[i->first] != i->second) { return 0; } } return 1;}// Drivers codeint main(){ vector<int> a = { 2, 4, 5, 7, 5, 6 }, b = { 4, 2, 5, 5, 6, 7 }; int n = a.size(), m = b.size(); bool flag = isEqual(a, b, n, m); // Return 1 if equal if (flag) { cout << "YES\n"; } else { cout << "NO\n"; } return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { public static boolean isEqual(int a[], int b[], int n, int m) { // If size is not same return false if (n != m) { return false; } // Create 2 unordered maps to store // the frequency HashMap<Integer, Integer> mp1 = new HashMap<Integer, Integer>(); HashMap<Integer, Integer> mp2 = new HashMap<Integer, Integer>(); for (int i : a) { if (mp1.get(i) != null) mp1.put(i, mp1.get(i) + 1); else mp1.put(i, 1); } for (int i : b) { if (mp2.get(i) != null) mp2.put(i, mp2.get(i) + 1); else mp2.put(i, 1); } // Compare the frequency for (Map.Entry<Integer, Integer> i : mp1.entrySet()) { Integer key = i.getKey(); // If frequency not same return false if (mp2.get(key) != i.getValue()) { return false; } } return true; } // Driver Code public static void main(String[] args) { int a[] = { 2, 4, 5, 7, 5, 6 }; int b[] = { 4, 2, 5, 5, 6, 7 }; int n = a.length, m = b.length; boolean flag = isEqual(a, b, n, m); // Return 1 if equal if (flag == true) { System.out.print("YES\n"); } else { System.out.print("NO\n"); } }}// This code is contributed by Rohit Pradhan |
Python3
# Python3 code to implement the approachdef isEqual(a, b, n, m) : # If size is not same return false if (n != m) : return 0 # Create 2 unordered maps to store # the frequency mp1 = dict.fromkeys(a, 0); mp2 = dict.fromkeys(b, 0); for i in a : if i in mp1 : mp1[i] += 1; else: mp1[i] = 0 for i in b : if i in mp2 : mp2[i] += 1; else : mp2[i] = 0 # Compare the frequency for i in mp1 : # If frequency not same return false if (mp2[i] != mp1[i]) : return 0; return 1;# Drivers codeif __name__ == "__main__" : a = [ 2, 4, 5, 7, 5, 6 ]; b = [ 4, 2, 5, 5, 6, 7 ]; n = len(a); m = len(b); flag = isEqual(a, b, n, m); # Return 1 if equal if (flag) : print("YES"); else : print("NO"); # This code is contributed by AnkThon |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;public class GFG { public static bool isEqual(int []a, int []b, int n, int m) { // If size is not same return false if (n != m) { return false; } // Create 2 unordered maps to store // the frequency Dictionary<int, int> mp1 = new Dictionary<int, int>(); Dictionary<int, int> mp2 = new Dictionary<int, int>(); foreach (int i in a) { if (mp1.ContainsKey(i)) mp1[i] = mp1[i] + 1; else mp1.Add(i, 1); } foreach (int i in b) { if (mp2.ContainsKey(i)) mp2[i] = mp2[i] + 1; else mp2.Add(i, 1); } // Compare the frequency foreach (KeyValuePair<int, int> i in mp1) { int key = i.Key; // If frequency not same return false if (mp2[key] != i.Value) { return false; } } return true; } // Driver Code public static void Main(String[] args) { int []a = { 2, 4, 5, 7, 5, 6 }; int []b = { 4, 2, 5, 5, 6, 7 }; int n = a.Length, m = b.Length; bool flag = isEqual(a, b, n, m); // Return 1 if equal if (flag == true) { Console.Write("YES\n"); } else { Console.Write("NO\n"); } }}// This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript code to implement the approachfunction isEqual(a, b, n, m){ // If size is not same return false if (n != m) { return false; } // Create 2 unordered maps to store // the frequency let mp1 = new Map(); let mp2 = new Map(); for (let i of a) { if (mp1.get(i) != null) mp1.set(i, mp1.get(i) + 1); else mp1.set(i, 1); } for (let i of b) { if (mp2.get(i) != null) mp2.set(i, mp2.get(i) + 1); else mp2.set(i, 1); } // Compare the frequency for (let i of mp1.keys()) { // If frequency not same return false if (mp2.get(i) != mp1.get(i)) { return false; } } return true;}// Driver Codelet a = [2, 4, 5, 7, 5, 6];let b = [4, 2, 5, 5, 6, 7];let n = a.length, m = b.length;let flag = isEqual(a, b, n, m);// Return 1 if equalif (flag == true) { document.write("YES<br>");}else { document.write("NO<br>");}// This code is contributed by Saurabh Jaiswal</script> |
Output
YES
Time complexity: O(N) in average case and O(N2) in worst case.
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
