Check if 2 arrays are similar without hashing or sorting

Question

We need to check if 2 arrays are similar or not. The elements can be duplicate as well. For example A = {2,3,4,5,6,6} and B = {3,6,2,4,6,5} are similar.

I have a naive solution :

foreach i:int in arr1
 foreach j:int in arr2
  {
    if(i == j)
     j = -1;
  } 

Now if all the elements of j are -1 , then we can say that the 2 arrays are similar. Can someone give a test case in which this won't work (i hope it should work though!) ?

Also this is O(n^2). Can we do better ? Sorting and Hashing are not allowed.

Answer 1

You can do it in O(max(L_A, L_B)) time, where L_A and L_B are lengths of A and B, respectively, but at the price of using O(M) space, where M is an allowed range of values in the arrays (i.e. there are such constants min and max, so that min <= a, b <= max holds true for every a in A and b in B).

seen = array[min..max]
foreach a in A
    seen[a] = 'a'

foreach b in B
    if seen[b] != 'a'
        // A didn't contain b
        return "A and B are not equivalent"
    else
       seen[b] = 'a,b'

foreach s in seen
    if s == 'a'
        // A did contain a which was not in B
        return "A and B are not equivalent"

return "A and B are equivalent"

This approach is practical if the arrays are very large, but all their values fit in a small range.

Answer 2

You can use a binary search tree that you build from one of them. Now go over the other one and check if the value is already in the binary search tree. This one runs in O(nlgn) and use O(n) space.