Check if two arrays are equal or not ?? eg: {1,2,3,4,5} == {4,5,3,2,1}

Question

Is there any problem with this approach ? or is it fine? we have to tell whether 2 arrays are equal as in the digits in them and their frequencies must be same irrespective of their order.

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

main(){

int t,n,i,in;
vector<int> x;

cin>>t;
while(t--){

   unordered_map<int,int> a,b;
   cin>>n;

   for(i=0;i<n;i++){
       cin>>in;
       x.push_back(in);
       a[in]++;
   }

   for(i=0;i<n;i++){
       cin>>in;
       b[in]++;
   }

   for(i=0;i<n;i++){

       if(b.find(x[i]) == b.end()){
           cout<<"0"<<endl;
           goto x;
       }

       if(a[x[i]] != b[x[i]]){
           cout<<"0"<<endl;
           goto x;
       }
   }

   cout<<"1"<<endl;
   x : ;
   }
}

On a scale of 0 to Chrome, you're getting really up there with useless memory usage. And you're not doing Chrome's job. — Blindy, May 28 '20 at 17:08
I recommend [learning from a good book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). Whatever you are learning from now is setting you up for failure. — user4581301, May 28 '20 at 17:11
Check out [`std::is_permutation`](https://en.cppreference.com/w/cpp/algorithm/is_permutation). — cigien, May 28 '20 at 17:12
Read the numbers into two vectors, then sort both vectors, then compare them. — Paul Sanders, May 28 '20 at 17:20
@PaulSanders that solution would be O(nlogn), i want it to be O(n) — Saheel Das, May 28 '20 at 17:37
@NathanOliver i need an O(n) solution, sorting takes O(nlogn) — Saheel Das, May 28 '20 at 17:50

score 0 · Accepted Answer · answered May 28 '20 at 17:28

I don't know how new you are to C++, so here is a possible solution with a few explanations.

#include <map>
#include <vector>
#include <iostream>

//Avoid using namespace std as it can cause problems with conflicts of names
//and other sorts of nasty issues
using std::cout;
using std::cin;
using std::map;
using std::vector;
using std::endl;

//By using an ordered map you can more easily compare them
//The arguments are passed as const (you will never modify them)
//and also as reference (&) since you don't need to copy them.
bool CheckIfEqual (const vector<int> & V1, const vector<int> & V2) {
    //If the vectors don't have the same size you can just return false
    if (V1.size() != V2.size()) {
        return false;
    }
    map <int, size_t> M1;
    map <int, size_t> M2;
    //This type of loop goes through all elements of the vector and 
    //either creates a corrisponding value in the map or, if it is
    //already present, it increases it to accout for repetitions.
    //Map is automatically sorted.
    for (auto & Elem : V1) {
        M1[Elem]++;
    }
    for (auto & Elem : V2) {
        M2[Elem]++;
    }
    return M1 == M2;
}

//The main function is used to provide some examples
int main () {
    //Expected output: true
    vector<int> V1 {1, 2, 3, 4, 5};
    vector<int> V2 {1, 2, 3, 4 ,5};
    cout << CheckIfEqual(V1, V2) << endl;

    //Expected output: true
    V1 = {1, 2, 3, 4, 5};
    V2 = {5, 3, 2, 1 ,4};
    cout << CheckIfEqual(V1, V2) << endl;

    //Expected output: false
    V1 =  {1, 2, 3};
    V2 =  {5, 3};
    cout << CheckIfEqual(V1, V2) << endl;

    //Expected output: false
    V1 =  {1, 2, 3, 4, 5};
    V2 = {5, 3, 2, 1 ,1};
    cout << CheckIfEqual(V1, V2) << endl;

    //Expected output: true
    V1 = {1, 5, 5, 4, 5};
    V2 = {5, 5, 5, 1 ,4};
    cout << CheckIfEqual(V1, V2) << endl;
}

The output is

Also please be very very careful when using goto, it is deprecated and only useful when you need to jump out of many nested loops all at once. A simple break would have worked better.

If I'm not wrong my solution should be O(n) since building a map is O(log(n)) and operator "==" is O(n). — User.cpp, May 28 '20 at 17:54
Building the map is O(NlogN) since there are `N` entries and each entry requires `O(logN)` for insertion. — NathanOliver, May 28 '20 at 17:57
Oh thanks for correcting, then I guess I have to say "I don't know", never used hashing before. — User.cpp, May 28 '20 at 18:01

Check if two arrays are equal or not ?? eg: {1,2,3,4,5} == {4,5,3,2,1}

1 Answers1