How to find reverse order pairs in two arrays?

Question

This is an interview question. There are two arrays A1 and A2. Find out the pairs of numbers in A2 which were in reverse order in A1. For example, A1 = [2 6 5 8 1 3], A2 = [1 2 3 4 5 6]. Answer: (1, 2), (1, 5), (1, 6), (5, 6), (3, 5), (3, 6).

O(N^2) algorithm is trivial. Is there any better algorithm ? What do you think ?

Answer 1

If you have a pattern like A1 = 1111122222 and A2 = 2222211111, then you'll output (N/2)⁴ pairs. Therefore you can't do any better than O(N⁴) in the worst case.

Below is an O(N⁴) solution that handles duplicates and some numbers occurring in only one of the two lists. Note that while it is O(N⁴) in the worst-case, it's average case of O(N²) is far more likely, similar to the complexity of quick-sort.

index = {} # dictionary of lists defaulting to []
for i in 0..len(A2):
  index[A2[i]].append(i)
for i1 in 0..len(A1):
  for j1 in i+1..len(A1):
    for i2 in index[A1[i1]]:
      for j2 in index[A1[j1]]:
        if i2 != j2 and i1 < j1 != i2 < j2:
          print A1[i1], A1[j1]

If we relax the output format slightly to allow outputting of (1, 2) * 7 to indicate 7 reversals, then we can do better. First zip the lists, giving [(2, 1), (6, 2), (5, 3), (8, 4), (1, 5), (3, 6)] for the example. Sort the arrays using a stable sort: first using the first item in each tuple, then sort another copy of the list using the second item in the tuple. Then use an adapted merge sort like the one mentioned here, but instead of counting we produce we output the inversions. This is an O(NlogN) solution.

Answer 2

If both arrays have same elements and A1 is a rearrange of A2(which is sorted) then we can modify Merge Sort to count number of inversions present in A1.

http://geeksforgeeks.org/?p=3968