- Mistake made: I was trying to iterate nums from the very beginning which can not solve this problem. Binary search tree can be used to count. The key is scan the array forwards or backwards.
class TreeNode {
public int val, pos, cnt;
public TreeNode left, right;
public TreeNode(int v, int p){
this.val = v;
this.pos = p;
cnt = 1;
}
}
public class Solution {
private TreeNode root = null;
private int insertNode(TreeNode n, TreeNode candidate){
if (n == null){
root = candidate;
return 0;
}
int smallerNumersCnt = 0;
while (n!=null){
if(candidate.val >= n.val){
if (candidate.val == n.val){
smallerNumersCnt += n.cnt -1;
} else {
smallerNumersCnt += n.cnt;
}
if (n.right!=null){
n = n.right;
} else {
n.right = candidate;
break;
}
} else {
n.cnt++;
if(n.left != null){
n = n.left;
} else {
n.left = candidate;
break;
}
}
}
return smallerNumersCnt;
}
public List<Integer> countSmaller(int[] nums) {
ArrayList<Integer> res = new ArrayList<>();
for (int i=nums.length-1; i>=0; --i){
res.add(0, insertNode(root, new TreeNode(nums[i], i)));
}
return res;
}
}