DEV Community

Carnato
Carnato

Posted on

Check two array are equal or not in O(n):🙄

Map is the solution of that problem

#include<bits/stdc++.h>
using namespace std;
int main()
{
   int a[]={1,2,5,4,0};
   int b[]={2,4,5,0,1};
   int n=5;
   //find that both array are equal in O(n)
   map<int,int>mp1;
   map<int,int>mp2;
   for(int i=0;i<n;i++)
   {
       mp1[a[i]]++;
       mp2[b[i]]++;
   }
   if(mp1==mp2)
   cout<<"both same";
   else
   cout<<"different";
    return 0;
}
Enter fullscreen mode Exit fullscreen mode

Discussion (1)

Collapse
fjones profile image
FJones
  1. It might be worth noting that you mean that the arrays contain the same elements but in arbitrary order. Equality of arrays is usually including the order.
  2. While this is indeed technically linear, it is also simply leveraging the operator == overload of map: cplusplus.com/reference/map/map/op...