import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/*https://www.youtube.com/watch?v=buDoT9ESw1c
*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]
* */
public class CountOfSmallerNumbersAfterSelf {
public static void main(String[] args) {
int[] arr ={7,5,2,6,1};
Node root = new Node(arr[arr.length-1]);
List<Integer> resultList = new ArrayList<>();
resultList.add(0);
for(int i=arr.length-2;i>=0;i--){
resultList.add(insertNode(root,arr[i]));
}
Collections.reverse(resultList);
System.out.println(resultList);
}
static int insertNode(Node root, int value){
int result = 0;
boolean isConnected = false;
while (!isConnected){
if(value<=root.value){
//apend in left
root.count++;
if(root.left==null){
Node newNode = new Node(value);
root.left = newNode;
isConnected = true;
}else{
root = root.left;
}
}else{
// append in right
result = result+root.count;
if(root.right==null){
Node newNode = new Node(value);
root.right = newNode;
isConnected = true;
}else{
root = root.right;
}
}
}
return result;
}
}
class Node{
Node left;
Node right;
int value;
int count=1;
public Node(int value){
this.value = value;
}
}
