# Count of Smaller Numbers After Self

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

Solution I: Bit manipulation

https://leetcode.com/discuss/74994/nlogn-divide-and-conquer-java-solution-based-bit-comparison

Solution II: Merge sort

https://leetcode.com/discuss/74110/11ms-java-solution-using-merge-sort-with-explanation

Solution III: Binary search tree

https://leetcode.com/discuss/73803/easiest-java-solution

10ms

``````public class Solution {
public List<Integer> countSmaller(int[] nums) {
List<Integer> res = new ArrayList<>();
if(nums == null || nums.length == 0) return res;
TreeNode root = new TreeNode(nums[nums.length - 1]);
for(int i = nums.length - 2; i >= 0; i--) {
int count = insertNode(root, nums[i]);
}
Collections.reverse(res);
return res;
}

public int insertNode(TreeNode root, int val) {
int thisCount = 0;
while(true) {
if(val <= root.val) {
root.count++;
if(root.left == null) {
root.left = new TreeNode(val); break;
} else {
root = root.left;
}
} else {
thisCount += root.count;
if(root.right == null) {
root.right = new TreeNode(val); break;
} else {
root = root.right;
}
}
}
return thisCount;
}
}

class TreeNode {
TreeNode left;
TreeNode right;
int val;
int count = 1;
public TreeNode(int val) {
this.val = val;
}
}
``````

Solution IV: Binary search

53ms

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

Solution V: Segment tree

https://leetcode.com/discuss/73233/complicated-segmentree-solution-hope-to-find-a-better-one

``````public class Solution {
static class segmentTreeNode {
int start, end, count;
segmentTreeNode left, right;
segmentTreeNode(int start, int end, int count) {
this.start = start;
this.end = end;
this.count = count;
left = null;
right = null;
}
}
public static List<Integer> countSmaller(int[] nums) {
List<Integer> result = new ArrayList<Integer>();

int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for (int i : nums) {
min = Math.min(min, i);

}
if (min < 0) {
for (int i = 0; i < nums.length; i++) {
nums[i] -= min;//deal with negative numbers, seems a dummy way
}
}
for (int i : nums) {
max = Math.max(max, i);
}
segmentTreeNode root = build(0, max);
for (int i = 0; i < nums.length; i++) {
}
for (int i = 0; i < nums.length; i++) {
updateDel(root, nums[i]);
}
return result;
}
public static segmentTreeNode build(int start, int end) {
if (start > end) return null;
if (start == end) return new segmentTreeNode(start, end, 0);
int mid = (start + end) / 2;
segmentTreeNode root = new segmentTreeNode(start, end, 0);
root.left = build(start, mid);
root.right = build(mid + 1, end);
root.count = root.left.count + root.right.count;
return root;
}

public static int query(segmentTreeNode root, int start, int end) {
if (root == null) return 0;
if (root.start == start && root.end == end) return root.count;
int mid = (root.start + root.end) / 2;
if (end < mid) {
return query(root.left, start, end);
} else if (start > end) {
return query(root.right, start, end);
} else {
return query(root.left, start, mid) + query(root.right, mid + 1, end);
}
}

public static void updateAdd(segmentTreeNode root, int val) {
if (root == null || root.start > val || root.end < val) return;
if (root.start == val && root.end == val) {
root.count ++;
return;
}
int mid = (root.start + root.end) / 2;
if (val <= mid) {
} else {
}
root.count = root.left.count + root.right.count;
}

public static void updateDel(segmentTreeNode root, int val) {
if (root == null || root.start > val || root.end < val) return;
if (root.start == val && root.end == val) {
root.count --;
return;
}
int mid = (root.start + root.end) / 2;
if (val <= mid) {
updateDel(root.left, val);
} else {
updateDel(root.right, val);
}
root.count = root.left.count + root.right.count;
}
}
``````

Solution VI: Binary Indexed tree

https://leetcode.com/discuss/73233/complicated-segmentree-solution-hope-to-find-a-better-one

``````public class Solution {

private void add(int[] bit, int i, int val) {
for (; i < bit.length; i += i & -i) bit[i] += val;
}

private int query(int[] bit, int i) {
int ans = 0;
for (; i > 0; i -= i & -i) ans += bit[i];
return ans;
}

public List<Integer> countSmaller(int[] nums) {
int[] tmp = nums.clone();
Arrays.sort(tmp);
for (int i = 0; i < nums.length; i++) nums[i] = Arrays.binarySearch(tmp, nums[i]) + 1;
int[] bit = new int[nums.length + 1];
Integer[] ans = new Integer[nums.length];
for (int i = nums.length - 1; i >= 0; i--) {
ans[i] = query(bit, nums[i] - 1);