Count of Smaller Numbers After Self [LeetCode] | Training dragons the hard way - Programming Every Day!
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].
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].
Solution In this post, I'm going to write a little bit about Binary Indexed Tree and its application to solve the above problem. The problem itself is not really hard. We can solve it using many ways, including Binary Search Tree, Segment Tree, Sorting, or language specific way such as using
lower_bound in C++, TreeSet (or SortedSet) in Java with method
lower (see some at the end) .
Once we know how to use Binary Indexed Tree or shortly BIT, we can solve many other problems, especially in programming contests since BIT is very easy to implement.
I suggest that you spend some time to read this article from Topcoder:
Binary Indexed Tree.
Basically, in this problem, we use BIT to count the number of integers that are less than a specific number.
Suppose that a number
N = A1B > 0 in binary representation, where
B contains all
0 . The array
tree is a BIT where
tree[N] count the number of integers that are from
A0B and
A1B - 1 .
So if we call
f[N] is the number of integers that are less than N, how we calculate its value?
Yes, you are correct,
f[N] = tree[N] + f[A0B] (where
A0B is in binary representation).
We also know that
A0B = N & (N-1) using bit manipulation. (NOTE: on the Topcoder, they use
A0B= N - (N & -N) .
Having this in mind, to solve the problem we run from the back of the array, try each element. At the position
i , we can simply calculate
f[nums[i]] and put it into the result. However, we need to update the BIT here, because we have found another integer. So the natural question is which element we need to update in the BIT? Obviously, we need to update
tree[N+1] by increasing its value by 1. But we do not stop there. Let
N+1 = C1D where
D has all
0 . As you can see, let
g[N+1] = C1D + 1D , we need to update
g[N+1] also. And in turn, we need to update
g[g[N+1]],so on...
Read full article from Count of Smaller Numbers After Self [LeetCode] | Training dragons the hard way - Programming Every Day!
.