Problem_315. Count of Smaller Numbers After Self - xwu36/LeetCode GitHub Wiki

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

Counting Inversions Via Binary Search Tree (BST)

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> list = new ArrayList<>();
        if(nums == null || nums.length == 0)
            return list;
        int n = nums.length;
        list.add(0);
        Node root = new Node(nums[n - 1]);
        for(int i = n - 2; i >= 0; i--){
            int tmp = insert(root, nums[i]);
            list.add(tmp);
        }
        Collections.reverse(list);
        return list;
    }
    
    public int insert(Node node, int cur){
        int smaller = 0;
        if(node.val == cur){
            smaller = node.childCount - node.selfCount;
            node.childCount++;
            node.selfCount++;
        }else if(node.val > cur){
            node.childCount++;
            if(node.left == null)
                node.left = new Node(cur);
            else
                smaller += insert(node.left, cur);
        }else{
            smaller = node.childCount;
            if(node.right == null)
                node.right = new Node(cur);
            else
                smaller += insert(node.right, cur);
        }
        return smaller;
    }
    
    class Node{
        int childCount = 1;
        int selfCount = 1;
        int val = 0;
        Node left;
        Node right;
        Node(int val){
            this.val = val;
        }
    }
}