Check if two arrays are equal or not

Difficulty Level Medium
Frequently asked in Accenture Goldman Sachs MAQ o9 solutions Taxi4Sure Twilio
Array Hash SortingViews 3099

The problem “Check if two arrays are equal or not” states that you are given two arrays. The problem statement says that you have to determine if given arrays are equal or not.

Check if two arrays are equal or not

Example

arr1[] = { 1, 4, 2, 5, 2 };
arr2[] = { 2, 1, 5, 4, 2 };
Yes, Arrays are equal !!
arr1[] = { 1, 3, 2, 7, 2 };
arr2[] = { 2, 1, 5, 3, 2 };
No, Arrays are not equal !!

Algorithm to Check if two arrays are equal or not

  1. Set the length of both the arrays to l1 and l2 respectively.
  2. Check if both of the lengths are not equal, if true, return false.
  3. Store and count the frequencies of each element into the map.
  4. Traversing the second array,
    1. Check if a map doesn’t contains arr2 elements, return false.
    2. Check if the frequency of that particular element is equal to 0 if true then return false.
    3. Reduce the frequency of the current element by 1, store it to that place of the frequency of the current element.
  5. Repeat 4th step until all the values are traversed.
  6. Return true.

Explanation

We are given a problem that asks to find out if the given two arrays are equal or not. To solve this we are going to use Hashing, it helps in saving our time and reduces time complexity.

The first thing we are going to do is to find out the length of both the arrays because for the condition, if arrays are equal, one condition should need to be fulfilled, and that is the length of both the arrays should be equal, so when we find the length of both of the arrays, we just need to check if equal or not, if it is not found to be equal we just return false and we do not need to proceed further. If it is found to be equal, then only we move further.

We will count and store the frequencies of each element of array1[] into the map. Suppose we find a single element twice or thrice, we just update and increase its frequency by 1 and store onto that same frequency along with that element.

Example

Let us consider an example:

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

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

After traversing the array1[]  and putting all the elements with their frequencies into the map we have the map as follows.

myMap={1:1, 2:2, 4:1, 5:1}

As we have the values in our map, we need to traverse the second array and check if a map is having array2 elements, if it doesn’t contain the array2[] elements then we return false. We will check, if the frequency of the current element is equal to 0, if it is found to be true then we return false. Then we take the value of the current element frequency and reduce it to by 1 and again put the value into the map. So, this will help for the next time if the same number exists for more than once. This condition is included in that case. Once we will come out of the loop, it means we have all the numbers similar in the array and make arrays equal. Then we will return true.

C++ code to Check if two arrays are equal or not

#include <unordered_map>
#include<iostream>

using namespace std;

bool areTwoArrayEqual(int arr1[], int arr2[], int l1, int l2)
{
    if (l1 !=l2)
        return false;

    unordered_map<int, int> myMap;
    for (int i = 0; i < l1; i++)
    {
        myMap[arr1[i]]++;
    }
    for (int i = 0; i < l1; i++)
    {
        if (myMap.find(arr2[i]) == myMap.end())
            return false;

        if (myMap[arr2[i]] == 0)
            return false;

        myMap[arr2[i]]--;
    }

    return true;
}
int main()
{
    int arr1[] = { 1, 4, 2, 5, 2 };
    int arr2[] = { 2, 1, 5, 4, 2 };

    int l1 = sizeof(arr1) / sizeof(int);
    int l2 = sizeof(arr2) / sizeof(int);

    if (areTwoArrayEqual(arr1, arr2, l1, l2))
        cout << "Yes, Arrays are equal !!";
    else
        cout << "No, Arrays are not equal !!";
    return 0;
}

Yes, Arrays are equal !!

Java code to Check if two arrays are equal or not

import java.util.*;

class twoArrayEqual
{
    public static boolean areTwoArrayEqual(int arr1[], int arr2[])
    {
        int l1 = arr1.length;
        int l2 = arr2.length;

        if (l1 != l2)
            return false;

        Map<Integer, Integer> myMap = new HashMap<Integer, Integer>();
        int count = 0;
        for (int i = 0; i < l1; i++)
        {
            if (myMap.get(arr1[i]) == null)
                myMap.put(arr1[i], 1);
            else
            {
                count = myMap.get(arr1[i]);
                count++;
                myMap.put(arr1[i], count);
            }
        }
        for (int i = 0; i < l1; i++)
        {
            if (!myMap.containsKey(arr2[i]))
                return false;

            if (myMap.get(arr2[i]) == 0)
                return false;

            count = myMap.get(arr2[i]);
            --count;
            myMap.put(arr2[i], count);
        }

        return true;
    }
    public static void main(String[] args)
    {
        int arr1[] = { 1, 4, 2, 5, 2 };
        int arr2[] = { 2, 1, 5, 4, 2 };

        if (areTwoArrayEqual(arr1, arr2))
            System.out.println("Yes, Arrays are equal !!");
        else
            System.out.println("No, Arrays are not equal !!");
    }
}

Yes, Arrays are equal !!

Complexity Analysis

Time Complexity

O(n) where “n” is the number of elements in the array. Using HashMap allowed us to achieve linear time complexity else it would have taken much more time.

Space Complexity

O(n) where “n” is the number of elements in the array. If all elements will be distinct, our map will have key-value for each of the numbers in the input. Thus space complexity is also linear.

Translate »