https://leetcode.com/problems/count-of-smaller-numbers-after-self/?tab=Description

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

1 | Example: |

#### cpp

C++ O(nlogn)-Time O(n)-Space MergeSort Solution with Detail Explanation

MergeSort-based solution is a standard way to solve problems related to inverse numbers.

Here is an example to illustrate the general idea of MergeSort-based algorithm:

Now we want to consider an array

1 | 6 4 1 8 7 5 2 9 |

First thing first, split the array into to subarrays:

1 | 6 4 1 8 |

and then calculate the inverse numbers within the group:

1 | 1 4(1) 6(1,4) 8 |

where the numbers in the parentheses are the numbers that should be counted when we calculate the inverse number.

Now we need to merge these two arrays into one sorted array. The first element to be put into the sorted destination array is the “1” in the first array.

1 | 1 4(1) 6(1,4) 8 |

The second element to merge is the “2” in the second array:

1 | 1 2 4(1) 6(1,4) 8 |

The third element to merge is the “4” in the first array:

1 | 1 2 4(1,2) 6(1,4) 8 |

When we merge the “4(1)”, we found that “4” is actually greater than all merged elements in the second array (i.e. [2]). Therefore, we also need to consider those elements. Therefore, the numbers in the parenthese of 2 become (1)+(2) = (1,2). Next step:

1 | 1 2 4(1,2) 5(2) 6(1,4) 8 |

Next (add the inverse number of element “6” by 2)

1 | 1 2 4(1,2) 5(2) 6(1,4,2,5) 8 |

So and so forth, finally reach

1 | 1 2 4(1,2) 5(2) 6(1,4,2,5) 7(2,5) 8(2,5,7) 9 |

Additionally, when we need to count the inverse number, we do not need to record the exact elements, we only need to record the numbers. So, we can use a variable to record the number of “merged elements in the 2nd array” (for example, semilen in the code beneath) and the number of smaller elements of each element (for example, results[idx] in the code beneath).

Complexities:

Time: O(n log n)

Space: O(n)

C++ Accepted Code:

1 | class Solution { |

https://discuss.leetcode.com/topic/31291/c-short-solution-using-binary-indexed-tree-56-ms

C++ short solution using binary indexed tree (56 ms)

1 | class Solution { |

https://discuss.leetcode.com/topic/36736/c-14-line-solution

C++ 14 line solution

1 | class Solution { |

#### python

https://discuss.leetcode.com/topic/31162/mergesort-solution

Mergesort solution

The smaller numbers on the right of a number are exactly those that jump from its right to its left during a stable sort. So I do mergesort with added tracking of those right-to-left jumps.

Update, new version

1 | def countSmaller(self, nums): |

Old version

1 | def countSmaller(self, nums): |

3 ways (Segment Tree, Binary Indexed Tree, Binary Search Tree) clean python code

Segment Tree

1 | class SegmentTreeNode(object): |

Binary Search Tree

1 | class BinarySearchTreeNode(object): |

#### java

10ms, 80.82%, October 18, 2016

https://discuss.leetcode.com/topic/31405/9ms-short-java-bst-solution-get-answer-when-building-bst

9ms short Java BST solution get answer when building BST

Every node will maintain a val sum recording the total of number on it’s left bottom side, dup counts the duplication. For example, [3, 2, 2, 6, 1], from back to beginning,we would have:

1 | 1(0, 1) |

When we try to insert a number, the total number of smaller number would be adding dup and sum of the nodes where we turn right.

for example, if we insert 5, it should be inserted on the way down to the right of 3, the nodes where we turn right is 1(0,1), 2,(0,2), 3(0,1), so the answer should be (0 + 1)+(0 + 2)+ (0 + 1) = 4

if we insert 7, the right-turning nodes are 1(0,1), 6(3,1), so answer should be (0 + 1) + (3 + 1) = 5

1 | public class Solution { |