Problem : Count of Smaller Numbers After Self
Description : You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i]
Solution :
My first approach was in time o(n2) . Start from right to left and lets suppose we are at position x having solved the part from x+ 1 to right
now count[x] = count { maximum of all the numbers smaller than x } + 1
but there is a better approach of time O(nlogn)
There are two approaches one based on merge sort and the other based on segment trees
Segment tree based Approach
Create a segment tree with interval [0, len(nums) — 1] . Note that a segment tree node consists of three parameters the value , the interval , and the children
Note that the segment tree should be in the interval 0 to len(nums) — 1 where nums contains distinct sorted numbers
Now sort the given array and keep a dictionary with key equal to the array element and the value equal to its index in sorted array
Now lets iterate through the array starting from last to first . In every iteration get the sorted position of the element from the dictionary and then get the sum of the segment tree with index (0, i -1) .
When we try to get the sum of segment tree we use i -1 because we want to know the answer to the question
Have we encountered any element whose sorted position is in between 0 .. i- 1
note that if we have we will get it in sum and that would the required value for element i
After getting the required value we need to update the tree saying that we have encountered an element with sorted index i
All these operations of segment tree take o(logn) time hence total time is 0(nlogn)
Note that in problem like this where you have to find the correct sorted position of an element in an array or In problem where you feel sorting would simplify the problem .The given approach works brilliantly.