Java O(nlogn) solution using BST with size information


  • 0
    J

    Use example of [5 4 7 3 6 1]
    Iterate from right to left. Let us say we are now at position 4, right numbers are 7,3,6,1. If we can find current 4 in the rank of right numbers, then the rank is the answer.
    The first way is to maintain a sorted array [1,3,6,7] of right numbers: we need two operation, add number 4, and rank it. No matter use linked list or simple array, one operation will be O(n), which will be no better than brute force.
    The other way is to use Tree structure, we can put the size information. So both the add and rank operation will be O(logn). Code is as below:

    public class Solution {
        private class TreeNode {
            private int size, val;
            private TreeNode left, right;
            public TreeNode(int val) {
                this.val=val;
                size=1;
            }
        }
        public List<Integer> countSmaller(int[] nums) {
            TreeNode root=null;
            LinkedList<Integer> res=new LinkedList<>();
            for (int i=nums.length-1; i>=0; i--) {
                root=add(root,nums[i]);
                res.addFirst(rank(root,nums[i]));
            }
            return res;
        }
        private TreeNode add(TreeNode x, int val) {
            if (x==null) return new TreeNode(val);
            if (val>x.val) x.right=add(x.right,val);
            else if (val<x.val) x.left=add(x.left,val);
            x.size++;
            return x;
        }
        private int rank(TreeNode x, int val) {
            if (x==null) return 0;
            if (val<x.val) return rank(x.left,val);
            if (val==x.val) return size(x.left);
            return x.size-size(x.right)+rank(x.right,val);
        }
        private int size(TreeNode x) {
            if (x==null) return 0;
            return x.size;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.