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/