# 315. Count of Smaller Numbers After Self (Hard)

https://leetcode.com/problems/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.
```

## Solutions

``````
class Solution {
public List<Integer> countSmaller(int[] nums) {
List<Integer> ans = new ArrayList<>();

if (nums == null || nums.length == 0) {
return ans;
}

List<Integer> sorted = new ArrayList<>();
for (int i = nums.length - 1; i >= 0; i--) {
int index = insert(sorted, nums[i]);

}

return ans;
}

private int insert(List<Integer> sorted, int target) {
if (sorted.size() == 0) {

return 0;
}

int left = 0;
int right = sorted.size() - 1;

// Do not forget the equal numbers
if (sorted.get(left) >= target) {

return 0;
}

if (sorted.get(right) < target) {

return right + 1;
}

// [1,3,3], 3, left 0, right 2
// [1,3,5,7], 3, left 0, right 4
// [1,1,1,3,3], 3, left 0, right 4

while (left < right) {

// No need to take account of overflow issue
int mid = (right + left) / 2; // mid=1

if (sorted.get(mid) < target) {
left = mid + 1;
}
// sorted.get(mid) 3 >= target 3,
else {
right = mid - 1; // right=1-1=0
}
}

// to reach here, left == right or left - right == 1
// mid==left, and right=mid-1

// [xxx, 1,3,4], left points to 1, right points to 3, insert after 1, left+1
// [xxx, 1,3,4], left points to 3, left points to 4, edge off 3, left
int idx = left;
if (sorted.get(left) < target) {
idx = left + 1;
}