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/