For each element of an unordered array output the number of greater elements

Question

I guess question is quite straight forward, so let me explain with an example

Input Array     = {3 1 8 2 5 3 6 7};
Output Required = {4,7,0,6,3,4,2,1};

Greater than 3 are 4 elements in array (5,6,7,8)
Greater than 1 are 7 elements in array (2,3,3,5,6,7,8)
Greater than 8 are 0 elements in array ()
Greater than 2 are 6 elements in array (3,3,5,6,7,8)
Greater than 5 are 3 elements in array (6,7,8)
Greater than 3 are 4 elements in array (5,6,7,8)
Greater than 6 are 2 elements in array (7,8)
Greater than 7 are 1 elements in array (8)

So one approach will be just to run two nested for loops and be done with it,
time complexity O(N^2), space complexity O(1)

How this can be further optimized?

Answer 1

If you create a copy of the list and sort it, then (assuming unique elements), the 'greater element count' for a value is just
(total number of elements - 1 - position of value in sorted_list),
where we subtract 1 since indices start at 0 and we only want strictly greater elements.

When elements can be repeated, we should now find the unique elements of the original list and sort them, but also keep track of how many times each element appeared. Then, we need the 'weighted position' of each value in the sorted list, which is the sum of counts of all values at or before that index.

After creating a mapping from each unique value to the count of strictly greater elements, iterate over the original list, replacing each element with the count it's been mapped to.

Since we can convert between 'greater element counts' and the full sorted list in linear time, this method is asymptotically optimal, as it finds greater element counts in O(n log n) time.

Here's a short Python implementation of that idea.

def greater_element_counts(arr: List[int]) -> List[int]:
    """Return a list with the number of strictly larger elements
    in arr for each position in arr."""

    element_to_counts = collections.Counter(arr)

    unique_sorted_elements = sorted(element_to_counts.keys())

    greater_element_count = len(arr)
    answer_by_element = {}

    for unique_element in unique_sorted_elements:
        greater_element_count -= element_to_counts[unique_element]
        answer_by_element[unique_element] = greater_element_count

    return [answer_by_element[element] for element in arr]