Count Smaller After Self

Problem

Return a list where result[i] is the number of elements to the right of i that are smaller than nums[i].

Coordinate-compress the values and sweep from right to left with a Fenwick tree, querying how many already-seen ranks are below the current one. Return an empty list for empty input.

Hint

The Fenwick tree stores counts of ranks seen so far; query below the current rank.

Test cases

case 1

in: [[5,2,6,1]]

expected: [2,1,1,0]

case 2

in: [[-1]]

expected: [0]

case 3

in: [[-1,-1]]

expected: [0,0]

case 4

in: [[3,4,9,6,1]]

expected: [1,1,2,1,0]

case 5

in: [[]]

expected: []

Starter codePython

def count_smaller_after_self(nums):
    # Your code here
    pass

5 test cases · run your code against them in the editor