I got this question during an interview and can't determine a solution better than O(n^2):

Define a "superior" of an element of a list to be another element that is later and strictly greater.

Write a function that takes in a list of numbers and returns the number of superiors for each element in the input list.

Example: [1, 3, 5, 2, 3, 6] -> [5, 2, 1, 2, 1, 0]

What are some approaches that can be used to solve this problem in O(n) time complexity?

CodePudding user response：

This can't be done worst-case faster than O(n log n), since you can sort a list of numbers by running this twice. If you know the number of elements that are later and strictly greater, you can reverse the list and run the algorithm again for elements that are earlier and strictly greater, after which you just place every element according to its rank.

For an O(n log n) solution, any sorted collection that can be modified to support order statistics will work, such as a balanced binary search tree. You can also use a Binary Indexed Tree to achieve this with much less code.

1. Make a sorted copy of your list L, so that you know every element's rank (i.e., their index in the sorted list).
2. Make a binary-indexed tree of the same length as L to track which numbers we've seen. The base array A is initially all zero, but we'll set A[i] to 1 after we see the ith ranked element
3. Iterate over the original list L. At iteration i, the number of superiors of L[i] is the number of elements after index i greater than L[i]. The prefix sum of A[0..rank(L[i])] tells you the number of elements earlier that are smaller, so rank(L[i]) minus that sum tells you the number of elements later that are smaller, from which we get the superiors by subtracting from |L|-i.
4. Update the binary indexed tree as if we had set A[rank(L[i])] to 1.