# Small Count Binary Search

Hard

### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Given an array `A` containing `N` elements, construct a new array `countSmaller[]` such that `countSmaller[i]` contains count of smaller elements on right side of each element `A[i]` in the array where `(0 <= i < N)`.

See original problem statement here

#### For Example:

``````Input  : A = [6, 4, 2, 1, 5]

Output : R = [4, 2, 1, 0, 0]

Explanation :

6 has 4 elements smaller than it on its right i.e. (4, 2, 1, 5)

4 has 2 elements smaller than it on its right i.e. (2, 1)

2 has 1 element smaller than it on its right i.e. (1)

1 has 0 element smaller than it on its right.

5 has 0 element smaller than it on its right.``````

### OBSERVATION:

1. If the value of `N` is greater than `10^5`, a `O(N^2)` solution will lead to a `TLE` and a `O(N)` solution is not possible for this problem, so we should look for a in-between solution.

2. Solving the problem in `O(NlogN)` would be great, where `O(N)` would be required for the array traversal only, we are left with `O(logN)`.

3. So this gives us an intuition that may be `Binary Search` can do our work here.

### SOLVING APPROACH:

1. The idea is to use `Binary Search`.

2. Create an empty vector to store elements in a sorted manner.

3. Start traversing the array from `right` to `left` and find the position of the current element in the vector where it should be placed to maintain the sorted property of the vector.

4. `Binary Search` will be used to find such position. Then insert the element at that position and the position itself will tell the elements smaller than the current element in the vector as it is already sorted. Store this value in a `result` array for every such element.

5. Print the `result` array.

### SOLUTIONS:

```
#include <bits/stdc++.h>
using namespace std;

/* function for inserting array elements from right to left
in a sorted manner in a vector and finding count of small
elements in the array to the right of each element*/
void insert(vector<int> &v, int num, int* res, int i) {

/* Initialise with start and end index of vector */
int low = 0;
int high = v.size() - 1;
while (low <= high) {

//finding a mid index
int mid = (low + high) / 2;

//finding value at mid index
int M = v[mid];

/* if mid element is greater than or equal to
num, search in the left half */
if (M >= num) {
high = mid - 1;
} else {

/* else search in the right half also notice low is
also the count of elements currently less than num */
low = mid + 1;
}
}
/* therefore low is the index where num should be placed
as elements to the left are all less than num*/
v.insert(v.begin() + low, num);

/* also indicate the elements less than num in the resultant array */
res[i] = low;
}

void countSmaller(int *arr, int n) {

/* resultant array that stores count of lesser elements */
int res[n] = {0};

/* vector for determing the position of an element and
inserting them accordingly */
vector<int> v;
for (int i = n - 1; i >= 0; i--) {
insert(v, arr[i], res, i);
}

/* print the resultant array */
for (int i=0; i<n; i++)
cout<<res[i]<<" ";

}

int main() {
int t; cin>>t;
while(t--){
int n; cin>>n;
int arr[n];
for(int i=0; i<n; i++)
cin>>arr[i];

countSmaller(arr, n);
cout<<"\n";
}
return 0;
}
```
```
import java.io.*;
import java.util.*;

public class Main {
public static void main(String[] args) throws IOException {

Scanner sc = new Scanner(System.in);
int t=sc.nextInt();
while(t-->0)
{
int n=sc.nextInt();
int []arr = new int[n];
for(int i=0;i<n;i++)
arr[i]=sc.nextInt();
List<Integer> nlist=countSmallerBinary(arr);
for (Integer integer : nlist)
System.out.print(integer + " ");
System.out.println();
}
}
private static List<Integer> countSmallerBinary(int[] nums) {
Integer[] res = new Integer[nums.length];
List<Integer> list = new ArrayList<>();
for (int i = nums.length - 1; i >= 0; i--) {
insert(list, nums[i], res, i);
}
return Arrays.asList(res);
}

private static void insert(List<Integer> list, int num, Integer[] res, int i) {
int lo = 0;
int hi = list.size() - 1;

while (lo <= hi) {
int mid = (lo + hi) / 2;
int M = list.get(mid);
if (M >= num) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}