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]
public List<Integer> countSmaller(int[] nums) {
Integer[] arr = new Integer[nums.length];
ArrayList<Integer> sorted = new ArrayList<Integer>();
for (int i = nums.length-1; i >= 0; i--) {
int index = getIndex(sorted, nums[i]);
arr[i] = index;
sorted.add(index, nums[i]);
}
return Arrays.asList(arr);
}
private int getIndex(ArrayList<Integer> sorted,int target) {
if (sorted.size()==0) {
return 0;
}
int start = 0;
int end = sorted.size()-1;
if (sorted.get(end)<target) {
return end+1;
}
if (sorted.get(start)>target) {
return 0;
}
while (start<end) {
int mid = (start+end)/2;
if (sorted.get(mid)<target) {
start = mid+1;
} else {
end = mid;
}
}
return start;
}
.```