You are currently viewing Check If Two Arrays Are Equal in C++
Equal array check

Check If Two Arrays Are Equal in C++

Check If Two Arrays Are Equal

Check If Two Arrays Are Equal

Greetings, Fellow Coders!

Welcome back to another exciting journey into the realm of algorithms and problem-solving! Today, we have an interesting problem “Check If Two Arrays Are Equal Array” on our hands: determining whether two arrays are equal or not. But wait, there’s a twist! These arrays might have the same elements, but they could be arranged differently. Let’s delve into the problem statement and explore two different solutions to tackle it.

Problem Description:

Given two arrays, A and B, both of size N, we need to ascertain if they are equal. Here’s the catch: two arrays are considered equal if they have the same set of elements. However, the arrangement of elements might differ. Additionally, if there are repetitions, the counts of repeated elements must match in both arrays for them to be considered equal.

Example Scenarios:

Let’s take a couple of examples to illustrate the problem:

Example 1:

Input:
N = 5
A[] = {6, 1, 7, 4, 9}
B[] = {1, 4, 7, 9, 6}
Output: 1

In this scenario, arrays A and B have the same elements, just arranged differently. Hence, the output is 1, indicating equality.

Example 2:

Input:
N = 3
A[] = {17, 12, 51}
B[] = {21, 14, 5}
Output: 0

Here, arrays A and B don’t have the same elements. Therefore, the output is 0, indicating inequality.

Solution 1: Sorting Approach

In the first solution, we employ a straightforward approach. We sort both arrays A and B and then compare their elements. If at any index i, the elements are different, we conclude that the arrays are not equal.

Step-by-Step Guide:

  • Sort both arrays A and B.
  • Iterate through each index i from 0 to N−1.
  • Compare the elements at the corresponding indices in both arrays.
  • If any elements are different, return false, indicating inequality.
  • If all elements match, return true, indicating equality.

Time Complexity: 

Sorting both arrays takes O(NlogN), and the comparison step takes O(N), resulting in a total time complexity of O(NlogN).

Code:

#include <bits/stdc++.h>
using namespace std;

bool checkEqualitySorting(vector<int>& A, vector<int>& B) {
    int N = A.size();
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    for (int i = 0; i < N; ++i) {
        if (A[i] != B[i])
            return false;
    }
    return true;
}

int main() {
    // Example 1
    vector<int> A1 = {6, 1, 7, 4, 9};
    vector<int> B1 = {1, 4, 7, 9, 6};
    cout << "Example 1: " << (checkEqualitySorting(A1, B1) ? "Equal" : "Not Equal") << endl;

    // Example 2
    vector<int> A2 = {17, 12, 51};
    vector B2 = {21, 14, 5};
    cout << "Example 2: " << (checkEqualitySorting(A2, B2) ? "Equal" : "Not Equal") << endl;

    return 0;
}

Solution 2: HashMap Approach

The second solution employs a HashMap to efficiently check for array equality. We iterate through array A, storing the frequency of each element in the HashMap. Then, we iterate through array B and decrement the frequency of each encountered element. If any element’s frequency becomes zero or if an element from array B is not found in the HashMap, we conclude inequality.

Step-by-Step Guide:

  • Create an unordered map to store the frequency of elements in array A.
  • Iterate through array A and update the frequency count in the map.
  • Iterate through array B.
  • If an element is not found in the map or its frequency becomes zero, return false, indicating inequality.
  • If all elements are found with matching frequencies, return true, indicating equality.

Time Complexity: 

Building the HashMap takes O(N), and iterating through array B and performing lookups in the map also takes O(N), resulting in a total time complexity of O(N).

Code:

#include <bits/stdc++.h>
using namespace std;

// Solution 2: HashMap Approach
bool checkEqualityHashMap(vector<int>& A, vector<int>& B) {
    int N = A.size();
    unordered_map<int, int> frequencyMap;
    for (int num : A)
        frequencyMap[num]++;
    
    for (int num : B) {
        if (frequencyMap.find(num) == frequencyMap.end() || frequencyMap[num] == 0)
            return false;
        frequencyMap[num]--;
    }
    return true;
}

int main() {
    // Example 1
    vector<int> A1 = {6, 1, 7, 4, 9};
    vector<int> B1 = {1, 4, 7, 9, 6};
    cout << "Example 1: " << (checkEqualityHashMap(A1, B1) ? "Equal" : "Not Equal") << endl;

    // Example 2
    vector<int> A2 = {17, 12, 51};
    vector<int> B2 = {21, 14, 5};
    cout << "Example 2: " << (checkEqualityHashMap(A2, B2) ? "Equal" : "Not Equal") << endl;

    return 0;
}

Conclusion:

In conclusion, we’ve explored two distinct approaches to solve the problem of checking array equality. While the sorting approach offers a straightforward solution, the HashMap approach provides a more efficient solution with a linear time complexity. The choice between these solutions depends on the specific requirements of the problem and the size of the input arrays.
Happy Coding!

Leave a Reply