Geek Answers Handbook

Check if 2 arrays match without hashing or sorting

We need to check if 2 arrays are similar or not. Elements can also be duplicates. 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 elements of j are equal to -1, we can say that 2 arrays are similar. Can someone give a test case in which this does not work (I hope it will work!)?

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

+5
source share
4 answers

, . , . O (nlgn) O (n) .

+3

O (max (L A, L B)) , L A L B - A B , O (M) , M - (.. min max, min <= a, b <= max a A b 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"

, , .

+5

A = {2,3,4, 5, -1,6} B = {3,6,2,4,6,5}

break if-statement, ,

0

I just want to mention that u should not run your algorithm (whether it has complexity o (n * m) or max (n, m)) for all input combinations. Run your algorithm only if xor of all elements of both arrays is zero. that is, [0] xor a [1] xor ... b [0] xor ... b [n] = 0. otherwise, u can confidently say that arrays A and B are not equal.

0
source

More articles:


All Articles