Count of Smaller Numbers After Self

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].

The problem has couple approaches. The easiest one to understand is to use a BST. We add elements from right to left, each time we add a new element, we track the value and number of left children so far. Then we traverse the tree and each left children of a node is the one we want.

I didn't implement this approach, because it's too complicated to write. I found another approach which also takes O(nlogn) but with much shorter code: Using binary search.

In this approach, we create a new array, then we use binary search to find the position of each number (still from right to left) in the new array. Since we traverse the array from right to left, all numbers smaller than the one to be inserted are elements that are smaller right to current one. And the position we found is the number of elements that are smaller.

   public List<integer> countSmaller(int[] nums) {
        List<integer> rst = new ArrayList<>(nums.length);
        for (int i = 0; i < nums.length; i++)
            rst.add(0);
        List<integer> sorted = new ArrayList<>();
        
        for (int i = nums.length - 1; i >= 0; i--) {
            int left = 0, right = sorted.size();
            while (left < right) {
                int mid = (left + right) / 2;
                if (sorted.get(mid) < nums[i]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            rst.set(i, right);
            sorted.add(right, nums[i]);
        }
        return rst;
    }