Check if given two Arrays are equal (using Map)

0 0 5 minutes read

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 code
int 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 approach
import 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 approach
 
def 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 code
if __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 approach
using 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 approach
function 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 Code
 
let 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 equal
if (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(N²) 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 zambiatek!