315 Count of Smaller Numbers After Self

Problem:

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:

``````Given nums = [5, 2, 6, 1]

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.
``````

Return the array [2, 1, 1, 0].

Solutions:

Binary search insert

``````public class Solution {
public List<Integer> countSmaller(int[] nums) {
ArrayList<Integer> cand = new ArrayList<Integer>();
for (int i = nums.length - 1; i >= 0; i --) {
int left = 0, right = cand.size();
while(left < right) {
int mid = (right - left) / 2 + left;
if (cand.get(mid) < nums[i]) {
left = mid + 1;
}
else {
right = mid;
}
}
}
return result;
}
}
``````

Binary Search Tree

``````public class Solution {
private class Node {
public int val;
public int cnt;
public int leftSum;
public Node left;
public Node right;
public Node(int val) {
cnt = 1;
leftSum = 0;
this.val = val;
}
}
public List<Integer> countSmaller(int[] nums) {
Node root = null;
for(int i = nums.length - 1; i >= 0; i --) {
root = helper(res, nums[i], root, 0);
}
return res;
}
private Node helper(List<Integer> res, int val, Node root, int preNum) {
if(root == null) {
return new Node(val);
}
if(root.val == val) {
root.cnt ++;
}
else if(root.val > val) {
root.leftSum ++;
root.left = helper(res, val, root.left, preNum);
}
else {
root.right = helper(res, val, root.right, preNum + root.leftSum + root.cnt);
}
return root;
}
}
``````

Binary Indexed tree

``````public class Solution {
public List<Integer> countSmaller(int[] nums) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i ++) {
if (nums[i] < min) {
min = nums[i];
}
if (nums[i] > max) {
max = nums[i];
}
}
int diff = 1 - min;
for (int i = 0; i < nums.length; i ++) {
nums[i] += diff;
}
max += diff;
int[] sums = new int[max + 1];
for (int i = nums.length - 1; i >= 0; i --) {
update(sums, nums[i]);
}
return result;
}
private int getSum(int[] sums, int index) {
int sum = 0;
while (index > 0) {
sum += sums[index];
index -= index & (-index);
}
return sum;
}
private void update(int[] sums, int val) {
while (val < sums.length) {
sums[val] += 1;
val += val&(-val);
};
}
}
``````