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

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.

Answer 2

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 3

This can be solved by creating a binary search tree such that each node contains the size of its left subtree.

Values are added to the BST in reverse order of the original array. A sum is kept and each time we go right when adding a node, the current node being compared's size of the left subtree + 1 is added to the final sum (since the value being added is greater than that node and every value in its left subtree).

Building the tree is nlogn and once the tree is built, the sum will be the number of pairs.

Specially handling needs to be added for duplicate numbers depending on the requirements (i.e. if (4,3) shows up twice, should it be counted twice)

Answer 4

Right-to-left traversal, Red-Black tree where each node is augmented by the size of its respective subtree. So it takes O(logn) to find the number of elements below a given one.

Answer 5

As @jlewis42 points out, you can use a modified version of merge sort. I just wanted to add, you could use any of the standard comparison sort algorithms, as long as the worst-case running time is n log n, by "instrumenting" it to count inversions as it works. See also this near dupe.