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

https://leetcode.com/discuss/73762/9ms-short-java-bst-solution-get-answer-when-building-bst

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]); res.add(0); for(int i = nums.length - 2; i >= 0; i--) { int count = insertNode(root, nums[i]); res.add(count); } 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; sorted.add(index, nums[i]); } 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) { // write your code here 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++) { updateAdd(root, nums[i]); } for (int i = 0; i < nums.length; i++) { updateDel(root, nums[i]); result.add(query(root, 0, nums[i] - 1)); } 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) { updateAdd(root.left, val); } else { updateAdd(root.right, val); } 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); add(bit, nums[i], 1); } return Arrays.asList(ans); } }

Introduction to BIT:

https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/