Interview Question: Reverse pairs

Question

I got this for my interview:

Numbers are said to be "reverse ordered" if N[i] > N[j] for i < j. For example, in a list: 3 4 1 6 7 3, the reverse ordered items are (3,1) (4,1) (4,3) (6,3) (7,3).

How to get the number of pairs of reverse ordered items in O(nlogn) time.

Answer 1

It is possible to do this in O(n log n) time using a modified version of merge sort. Do the division as normal, but you can count inversions as you merge. Each time you select an item from the right list over an item from the left list increment the count of inversions by the number of items remaining in the left list. So at each level the number of inversions is the number of inversions found during the merge plus the inversions found by each recursive call.

Answer 2

Note, please read the bottom of this answer to see why it actually is possible to do the problem. I read the question wrong.

It is not possible in the general case. Consider the list:

n, n-1, n-2 ... 4, 3, 2, 1

The pairs will be:

(n, n-1), (n, n-2) ... (n, 2), (n, 1), (n-1, n-2), (n-1, n-3) ... ... (3, 2), (3, 1), (2, 1)

Hence there are O(n^2) pairs and hence the list cannot be build in O(n log n)

However, you can do this with one pass of the list:

1. start at the end of the list and work backwords.
2. while moving through the list maintain a heap of the numbers you have seen (this will cause the loop to be O(n log n))
3. for ever number you encounter do a search in the heap to find all numbers which are less than the number you are currently on. Output the current number and the number in the heap as a pair. (this is O(n log n) to find the first match in the heap, but will be O(n) to find all smaller numbers)

For your example:

The list: 3 4 1 6 7 3

starting at the second item

heap (3) item (7)

Output (7, 3)

heap (3, 7) item (6)

search and find 7, output (6, 3)

heap (3, 6, 7) item (1)

search and find nothing

heap (1, 3, 6, 7) item (4)

search and find 3 and 1. output (4, 3) (4, 1)

etc....

Edit, it is possible actually

Since JoshD correctly noted that we are looking for the number of elements, you can use a B-Tree instead of a heap and then you can get just the count of elements less than the current item and add it to a counter.