CODEWITHSUNDEEP
algorithmmerge
Raj
Raj

Reputation: 147

Optimized algorithm to synchronize two arrays

I am looking for an efficient algorithm to synchronize two arrays. Let's say a1 and a2 are two arrays given as input.

a1 - C , C++ , Java , C# , Perl

a2 - C++ , Python , Java , Cw , Haskel

Output 2 arrays:

Output A1: C , C++ , Java

Output A2: Cw , Haskell , Python

Output A1:

1) items common to both arrays 2) items only in A1 and not in A2

Output A2:

items only in a2

Thanks in advance.

Raj

Upvotes: 1

Views: 3008

Answers (1)

jdehaan
jdehaan

Reputation: 19938

  1. Sort both arrays with an efficient sorting algorithm, complexity of O(n.log(n))
  2. Build the output arrays initially empty
  3. Compare the first element a1 of sorted A1 to the first element a2 of sorted A2
    • Equal means is in both arrays, put a1 into OutputA1
    • a1 < a2 means a1 is only in A1, a1 now necomes next element in sorted A1, put a1 into OutputA1
    • else a2 < a1 means a2 is only in A2, a2 now necomes next element in sorted A2, put a2 into OutputA2

Do this until you processed all elements in the sorted arrays, complexity of O(n).

Upvotes: 7

Related Questions