# Solution :: Count of smaller Number after self

• ## Solutions

### Approach #1 (Naive double loop) [Time Limit Exceeded]

#### Java

``````import java.util.Arrays;

class Solution {
public List<Integer> countSmaller(int[] nums) {
Integer[] counts = new Integer[nums.length];
for (int i = 0; i < nums.length; i++) {
counts[i] = 0;
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[i]) {
counts[i] += 1;
}
}
}
return Arrays.asList(counts);
}
}
``````

O(n^2)

### Approach #2 (Modified Binary Search Tree) [Accepted]

Use a modified BST where each node keeps track of the number of nodes in the tree that have smaller values (number of left descendants). Let us call this extra field `leftWeight`.

• Starting from the right-most value in the input array, recursively insert nodes to the BST. For every index i, the BST is guaranteed to only have values at indexes > i.
• With every right-leaning move down the BST, keep track of the number of nodes that have values less than the current value.
• Update `leftWeight` accordingly with every left-leaning move down the BST.

#### Java

``````import java.util.Arrays;

class Solution {
private class TreeNode {
int val;
TreeNode left;
TreeNode right;
int leftWeight;

TreeNode(int val) {
this.val = val;
}
}

private Integer insertAndGetLessThanCount(TreeNode root, TreeNode node, int numLessThan) {
if (node.val <= root.val) { // insert to left
root.leftWeight += 1;
if (root.left == null) {
root.left = node;
return numLessThan;
} else {
return insertAndGetLessThanCount(root.left, node, numLessThan);
}
} else { // insert right
numLessThan += root.leftWeight + 1;
if (root.right == null) {
root.right = node;
return numLessThan;
} else {
return insertAndGetLessThanCount(root.right, node, numLessThan);
}
}
}

public List<Integer> countSmaller(int[] nums) {
Integer[] counts = new Integer[nums.length];
if (counts.length > 0) {
counts[nums.length-1] = 0;
TreeNode root = new TreeNode(nums[nums.length-1]);
for (int i = nums.length - 2; i >= 0; i--) {
TreeNode node = new TreeNode(nums[i]);
counts[i] = insertAndGetLessThanCount(root, node, 0);
}
}
return Arrays.asList(counts);
}
}
``````

#### Complexity Analysis

The time complexity of this approach is O(n * height of BST).

For a balanced BST the time complexity is O(nlogn).

For an extremly imbalanced BST the time complexity degrades to O(n^2).

The imbalanced case can be avoided by using a self-balancing BST such 2-3 tree, AVL tree, etc.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.