https://leetcode.com/problems/count-of-smaller-numbers-after-self/

count-of-smaller-numbers-after-self-v1.java

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        int len = nums.length;
        int[] indexes = new int[len];
        Integer[] res = new Integer[len];
        int[] temp = new int[len];
        for (int i = 0; i < len; i++) {
            indexes[i] = i;
            res[i] = 0;
        }
        mergeSort(nums, indexes, res, temp, 0, len - 1);
        return Arrays.asList(res);
    }
    
    public void mergeSort(int[] nums, int[] indexes, Integer[] res, int[] temp, int left, int right) {
        if (left >= right) {
            return;
        }
        
        int mid = left + (right - left) / 2;
        
        mergeSort(nums, indexes, res, temp, left, mid);
        mergeSort(nums, indexes, res, temp, mid + 1, right);
        
        int l = left;
        int r = mid + 1;
        int count = 0;
        int i = left;
        
        while(l <= mid && r <= right) {
            if (nums[indexes[l]] <= nums[indexes[r]]) {
                res[indexes[l]] += count;
                temp[i++] = indexes[l++];
            } else {
                count ++;
                temp[i++] = indexes[r++];
            }
        }
        
        while(l <= mid) { // r ended, l still not
            res[indexes[l]] += count;
            temp[i++] = indexes[l++];
        }
        while(r <= right) {
            temp[i++] = indexes[r++];
        }
        
        for (int k = left; k <= right; k++) {
            indexes[k] = temp[k];
        }
    }
    
}

count-of-smaller-numbers-after-self-v2.java

class Solution {
    class SegmentTreeNode {
        int start;
        int end;
        int sum;
        SegmentTreeNode left;
        SegmentTreeNode right;
        
        public SegmentTreeNode(int start, int end) {
            this.start = start;
            this.end = end;
            this.sum = 0;
        }
    }
    
    
    class SegmentTree {
        
        SegmentTreeNode root;
        
        public SegmentTree(int start, int end) {
            this.root = buildTree(start, end);
        }
        
        public SegmentTreeNode buildTree(int start, int end) {
            if (start > end) {
                return null;
            }
            
            SegmentTreeNode node = new SegmentTreeNode(start, end);
            if (start == end) {
                // val is 0
                return node;
            }
            int mid = start + (end - start) / 2;
            node.left = buildTree(start, mid);
            node.right = buildTree(mid + 1, end);
            // vals are all 0
            return node;
        }
        
        public void update(SegmentTreeNode node, int index, int val) {
            if (node.start == index && node.end == index) {
                node.sum += val;
                return;
            }
            int mid = node.start + (node.end - node.start) / 2;
            if (index <= mid) {
                update(node.left, index, val);
            } else {
                update(node.right, index, val);
            }
            node.sum = node.left.sum + node.right.sum;
        }
        
        public int querySum(SegmentTreeNode node, int i, int j) {
            if (node.start == i && node.end == j) {
                return node.sum;
            }
            int mid = node.start + (node.end - node.start) / 2;
            if (i > mid) {
                return querySum(node.right, i, j);
            }
            if (j <= mid) {
                return querySum(node.left, i, j);
            }
            return querySum(node.left, i, mid) + querySum(node.right, mid + 1, j);
        }
        
    }
    
    
    
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> result = new ArrayList<>();
        int[] arr = nums.clone();
        Arrays.sort(nums);
        Map<Integer, Integer> rank = new HashMap<>();
        int n = 1; // unique rank
        for (int i = 0; i < nums.length; i++) {
            if (i == 0 || nums[i - 1] != nums[i]) {
                rank.put(nums[i], n++);
            }
        }
        
        SegmentTree segTree = new SegmentTree(0, n);
        for (int i = arr.length - 1; i >= 0; i--) {
            int rankI = rank.get(arr[i]); 
            result.add(segTree.querySum(segTree.root, 0, rankI - 1));
            segTree.update(segTree.root, rankI, 1);
        }
        
        Collections.reverse(result);
        
        return result;
    }
}

count-of-smaller-numbers-after-self-v3.java

class Solution {
    
    class BinaryIndexedTree {
        int[] sum;
        
        public BinaryIndexedTree(int n) {
            this.sum = new int[n];
        }
        
        private int lowbit (int x) {
            return x & (-x);
        }
        
        public int query(int i) {
            int res = 0;
            while(i > 0) {
                res += this.sum[i];
                i -= lowbit(i);
            }
            return res;
        }
        
        public void update(int i, int val) {// add val
            while(i < sum.length) {
                sum[i] += val;
                i += lowbit(i);
            }
        }
        
    }
    
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> result = new ArrayList<>();
        int[] arr = nums.clone();
        Arrays.sort(nums);
        Map<Integer, Integer> rank = new HashMap<>();
        int n = 1; // unique rank
        for (int i = 0; i < nums.length; i++) {
            if (i == 0 || nums[i - 1] != nums[i]) {
                rank.put(nums[i], n++);
            }
        }
        
        BinaryIndexedTree bTree = new BinaryIndexedTree(n);
        
        for (int i = arr.length - 1; i >= 0; i--) {
            int rankI = rank.get(arr[i]);
            result.add(bTree.query(rankI - 1));
            bTree.update(rankI, 1);
        }
        
        Collections.reverse(result);
        return result;
    }
}

count-of-smaller-numbers-after-self-v4.java

class Solution {
    
    class BinaryTreeNode {
        int count;
        int leftCount; // count nodes of left sub tree
        int val;
        BinaryTreeNode left;
        BinaryTreeNode right;
        
        
        public BinaryTreeNode(int val) {
            this.val = val;
            this.count = 1;
            this.leftCount = 0;
        }
    }
    
    public int insert(BinaryTreeNode root, int val) {
       // base case
        BinaryTreeNode node = root;
        BinaryTreeNode pre = null;
        int res = 0;
        while(node != null) {
            if (node.val == val) {
                break;
            } else if (node.val > val) {
                // go left
                node.leftCount += 1;
                pre = node;
                node = node.left;
            } else {
                res += (node.count + node.leftCount); 
                pre = node;
                node = node.right;
            }
        }
        if (node != null) {
            res += node.leftCount;
            node.count += 1;
        } else if (pre.val > val) {
            pre.left = new BinaryTreeNode(val);
        } else {
            pre.right = new BinaryTreeNode(val);
        }
        return res;
    }
    
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        
        int n = nums.length;
        BinaryTreeNode root = new BinaryTreeNode(nums[n - 1]);
        result.add(0);
        for (int i = n - 2; i >= 0; i--) {
            result.add(insert(root, nums[i]));
        }
        Collections.reverse(result);
        return result;
    }
}