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

Solution

public class Solution {
 public List<Integer> countSmaller(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if (nums == null || nums.length == 0) return result;

        result.add(0);
        int size = nums.length;
        Node root = new Node(nums[size - 1]);
        for(int i = size -2; i >= 0; i --) {
            int temp = insertNode(root, nums[i]);
            result.add(0, temp);
        }
        return result;
    }

    private int insertNode(Node root, int val) {
        int thisCount = 0;
        while (true) {
            if (val <= root.val) {
                root.count += 1;
                if (root.left == null) {
                    root.left = new Node(val);
                    break;
                } else {
                    root = root.left;
                }
            } else {
                thisCount += root.count;
                if (root.right == null) {
                    root.right = new Node(val);
                    break;
                } else {
                    root = root.right;
                }
            }
        }

        return thisCount;
    }

    public class Node {
        Node left;
        Node right;
        int count;
        int val;

        public Node(int val) {
            this.val = val;
            this.count = 1;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public Node getRight() {
            return right;
        }

        public void setRight(Node right) {
            this.right = right;
        }

        public int getCount() {
            return count;
        }

        public void setCount(int count) {
            this.count = count;
        }
    }
}