# Question

Formatted question description: https://leetcode.ca/all/315.html

 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.



# Algorithm

You can start traversing from the right, and keep putting the traversed numbers into another sort array, and store this sort array in ascending order, So, if you are looking for a few smaller numbers to the right of the current value, then you have to find the position where the current value should be placed in the sort array (In order to improve efficiency, use the binary search method to determine where the current value should be placed), that is, there are several smaller numbers on the right.

example:

nums: [5,2,6,1] When i = 3, nums[i] =1, sort[0]=nums[i];

0 1 2 3     <= sort[] index
1           <= sort[] value


When i = 2, nums[i] = 6, by using the dichotomy search in sort (currently only element 1), it is found that 6 should be inserted after 1, [1,6], ie index=1, sort[index] =nums[i]; So the number of numbers smaller than it on the right of the current value 6 is index=1

0 1 2 3
1 6


When i = 1, nums[i] = 2, by using the dichotomy search in sort (currently only elements 1, 6), it is found that 2 should be inserted after 1, [1,2,6], ie index=1, sort[index]=nums[i]; So the number of numbers smaller than it on the right side of the current value 2 is index=1

0 1 2 3
1 2 6


When i = 0 and nums[i] = 5, by using the dichotomy search in sort (currently only elements 1, 2, 6), it is found that 5 should be inserted after 2, [1,2,5,6], that is index=2, sort[index]=nums[i]; So the number of numbers smaller than it on the right of the current value of 5 is index=2

0 1 2 3
1 2 5 6


Then, the result is Output: [2,1,1,0].

# Code

Java

• import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Count_of_Smaller_Numbers_After_Self {

public static void main(String[] args) {
Count_of_Smaller_Numbers_After_Self out = new Count_of_Smaller_Numbers_After_Self();
Solution s = out.new Solution();

System.out.println(s.countSmaller(new int[]{5,2,6,1}));
}

class Solution {
public List<Integer> countSmaller(int[] nums) {

List<Integer> result = new ArrayList<>();
List<Integer> sorted = new ArrayList<>();

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

for (int i = nums.length - 1; i >= 0; i--) {

// binary search for current pos, reference: Arrays.binarySearch()
int left = 0;
int right = sorted.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[i] <= sorted.get(mid)) {
right = mid;
} else {
left = mid + 1;
}
}

// now nums[i] should be placed at index left
sorted.add(left, nums[i]); // @note: equal to .insert()
result.add(0, left); // @note: insert to 1st node，因为是倒序scan array
}

return result;
}
}
}

• // OJ: https://leetcode.com/problems/count-of-smaller-numbers-after-self/
// Time: O(NlogN)
// Space: O(N)
class Solution {
vector<int> id, tmp, ans;
void solve(vector<int> &A, int begin, int end) {
if (begin + 1 >= end) return;
int mid = (begin + end) / 2, i = begin, j = mid, k = begin;
solve(A, begin, mid);
solve(A, mid, end);
for (; i < mid; ++i) {
while (j < end && A[id[j]] < A[id[i]]) {
tmp[k++] = id[j++];
}
ans[id[i]] += j - mid;
tmp[k++] = id[i];
}
for (; j < end; ++j) tmp[k++] = id[j];
for (int i = begin; i < end; ++i) id[i] = tmp[i];
}
public:
vector<int> countSmaller(vector<int>& A) {
int N = A.size();
id.assign(N, 0);
tmp.assign(N, 0);
ans.assign(N, 0);
iota(begin(id), end(id), 0);
solve(A, 0, N);
return ans;
}
};

• import bisect

class Solution(object):
def countSmaller(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
ans = []
bst = []
for num in reversed(nums):
idx = bisect.bisect_left(bst, num)
ans.append(idx)
bisect.insort(bst, num)
return ans[::-1]