315. Count of Smaller Numbers After Self

Description

You are given an integer arraynumsand you have to return a newcountsarray. Thecountsarray has the property wherecounts[i]is the number of smaller elements to the right ofnums[i].

Example:

Given 
nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Return the array[2, 1, 1, 0].

Solutions

method 1:

sort + map<val, sorted index> + BIT

sort(nlogn) + construct bit(nlogn) + query bit(nlogn)

method 2:

runtime sort array(binary search + array insert)

nlogn + cost of insertion