DEV Community

Vishal Yadav
Vishal Yadav

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

Top comments (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...