# 315. 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:

Input: [5,2,6,1]
Output: [2,1,1,0] 

Explanation:
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.

# Solution

Approach 1: O(NlogN) merge sort. Count the number of nums swapped from the right side to the left during the merge step.

Approach 2: O(NlogN) to O(N^2) binary search tree. Insert numbers from the back, use bst's property: inorder traversal yields a sorted array.

Approach 3: O(NlogN) binary index tree on frequency array of ranked nums.

# Code (Python)

Approach 1:

    def countSmaller(self, nums: List[int]) -> List[int]:
        # O(NlogN) merge sort idea: count the number of nums swapped from the right side to the left during the merge step
        if not nums:
            return []
        counts = [0 for _ in range(len(nums))]
        # [(index0, value0), ...] to remember its original index
        self._mergesort(list(enumerate(nums)), counts)
        return counts
    
    def _mergesort(self, nums, counts):
        # returns a new array -- mergesort is not an inplace sort
        if len(nums) == 1:
            return nums
        left_part = self._mergesort(nums[:len(nums)//2], counts)
        right_part = self._mergesort(nums[len(nums)//2:], counts)
        # use two pointers to merge two parts into nums
        l, r = 0, 0
        while l < len(left_part) or r < len(right_part):
            # every time we put in something on the left part, account how many elements on the right went before it. things on the right don't have to do this because we only count nums jumped from right to the left
            if r == len(right_part) or (l < len(left_part) and left_part[l][1] <= right_part[r][1]): # left_part[l][1] <= because we put left first to avoid a swap
                nums[r+l] = left_part[l]
                counts[left_part[l][0]] += r
                l += 1
            else:
                nums[r+l] = right_part[r]
                r += 1
        return nums
    
    # OR can also go backwards in the merge
    def countSmaller(self, nums):
        def sort(enum):
            half = len(enum) // 2
            if half:
                left, right = sort(enum[:half]), sort(enum[half:])
                for i in range(len(enum))[::-1]: # can also go backwards here
                    if not right or left and left[-1][1] > right[-1][1]:
                        smaller[left[-1][0]] += len(right)
                        enum[i] = left.pop()
                    else:
                        enum[i] = right.pop()
            return enum
        smaller = [0] * len(nums)
        sort(list(enumerate(nums)))
        return smaller

Approach 2:

class TreeNode:
    def __init__(self, val):
        self.left_nodes = 0 # num of elements(including repetitions) in left subtree -- meaning all nums less than it in the bst
        self.rep = 1 # num of repetitions of this value
        self.val = val
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None
        
    def insert(self, value):
        # returns num of nodes whose values are smaller than self
        if not self.root:
            self.root = TreeNode(value)
            return 0
        node = self.root
        num_smaller = 0
        # iteratively add a node into the bst
        while node:
            if value < node.val:
                node.left_nodes += 1
                if not node.left:
                    node.left = TreeNode(value)
                    return num_smaller
                node = node.left
            elif value > node.val:
                num_smaller += node.rep + node.left_nodes
                if not node.right:
                    node.right = TreeNode(value)
                    return num_smaller
                node = node.right
            else: # value == node.val
                node.rep += 1
                num_smaller += node.left_nodes
                return num_smaller
    
class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        if not nums:
            return []
        if len(nums) == 1:
            return [0]
        counts = [0] * len(nums)
        bst = BinarySearchTree()
        for i in range(len(nums) - 1, -1, -1):
            counts[i] = bst.insert(nums[i])
        return counts

Approach 3:

class BinaryIndexTree:
    def __init__(self, n):
        self._sums = [0] * (n + 1) # valid parts from 1 to n + 1, because you can't get lowbits of 0
    
    def update(self, delta, index):
        while index < len(self._sums):
            self._sums[index] += delta
            # increament the lowest bit for a number, e.g. lowbit(10110) = 10
            # - (10110) = 01001 + 1 = 10010
            index += (index & -index)
    
    def query(self, index):
        result = 0
        while index > 0:
            result += self._sums[index]
            index -= (index & -index)
        return result
    
class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        # think of a frequency array, where index of array correspond to the value of the num
        # put nums from the back to front into the frequency array, result for each number is the sum(freq_array[:num-1])
        # that's prefix sum with changing values -- use Binary Index Tree: https://www.youtube.com/watch?v=WbafSgetDDk
        # the values of nums can be "compressed" into just a ranks so that the freq array don't have to be that sparse
        ranks = {}
        for i, num in enumerate(sorted(nums)):
            if i == 0:
                ranks[num] = 1 # rank starts from 1
            else:
                if num != prev_num:
                    ranks[num] = ranks[prev_num] + 1
            prev_num = num
        
        tree = BinaryIndexTree(len(nums))
        result = [0] * len(nums)
        for i, num in enumerate(nums[::-1]):
            value = ranks[num]
            tree.update(1, value)
            result[i] = tree.query(value - 1)
        
        return result[::-1]

# Code (C++)

Approach 1:

// Merge sort.
class Solution {
private:
    vector<int> res;
    vector<int> oriToNew;
    vector<int> newToOri;
    void goMergeSort(vector<int>& nums, int head, int tail) {
        if (head >= tail)
            return;
        int mid = head + (tail - head) / 2;
        // Merge sort for sub arrays.
        goMergeSort(nums, head, mid);
        goMergeSort(nums, mid+1, tail);
        // Merge sort.
        vector<int> tmp;
        int i1 = head;
        int i2 = mid + 1;
        int offset = 0;
        while (i1 <= mid || i2 <= tail)
        {
            if (i2 > tail || i1 <= mid && nums[i1] <= nums[i2])
            {
                tmp.push_back(nums[i1]);
                oriToNew[newToOri[i1]] = head + tmp.size() - 1;
                res[newToOri[i1]] += offset;
                i1++;
            }
            else
            {
                tmp.push_back(nums[i2]);
                oriToNew[newToOri[i2]] = head + tmp.size() - 1;
                i2++;
                offset++;
            }
        }
        for (int i = head; i <= tail; ++i)
        {
            nums[i] = tmp[i-head];
            newToOri[oriToNew[i]] = i;
        }
    }
public:
    vector<int> countSmaller(vector<int>& nums) {
        for (int i = 0; i < nums.size(); ++i)
        {
            oriToNew.push_back(i);
            newToOri.push_back(i);
            res.push_back(0);
        }
        goMergeSort(nums, 0, nums.size()-1);
        return res;
    }
};

Approach 2:

// Binary search tree (BST).
class Solution {
    struct TreeNode {
        int val;
        int dupNum;
        int leftNum;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), dupNum(1), leftNum(0), left(NULL), right(NULL) {}
    };
private:
    int insertToBST(TreeNode *root, int value) {
        TreeNode *node = root;
        int smallerNum = 0;
        while (node)
        {
            if (value < node->val)
            {
                node->leftNum++;
                if (!node->left)
                {
                    node->left = new TreeNode(value);
                    break;
                }
                node = node->left;
            }
            else if (value > node->val)
            {
                smallerNum += node->dupNum + node->leftNum;
                if (!node->right)
                {
                    node->right = new TreeNode(value);
                    break;
                }
                node = node->right;
            }
            else
            {
                smallerNum += node->leftNum;
                node->dupNum++;
                break;
            }
        }
        return smallerNum;
    }
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> res;
        int n = nums.size();
        if (n == 0)
            return res;
        TreeNode root(nums[n-1]);
        res.push_back(0);
        for (int i = nums.size()-2; i >= 0; --i)
        {
            res.insert(res.begin(), insertToBST(&root, nums[i]));
        }
        return res;
    }
};