Easiest Java solution


  • 41

    Traverse from nums[len - 1] to nums[0], and build a binary search tree, which stores:

    1. val: value of nums[i]
    2. count: if val == root.val, there will be count number of smaller numbers on the right

    Run time is 10ms. Hope it helps!

    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;
    	}
    }

  • 0
    Q

    I think the complexity of this O(n^2). Probably should use self balancing tree.


  • 0

    You are right. For worth case. So it's not likely to implement an AVL tree in an interview. I think it's good enough for an interview. The run time for this problem is not bad.


  • 0
    Y

    first thanks @yavinci ‘s straightforward solution. As mentioned by @qgambit2, the worst case could be n^2 if the tree is not well balanced. But we can use builtin map, starting from the back of the array, we insert element to map, and use lower_bound to calculate how many element >= than the current element, then use map.size() minus this amount. The builtin map is automatic balanced.


  • 0

    @yueyub, that sounds an amazing solution! Could you share your solution here and I can make that the best answer.


  • 0
    H

    very concise, with good readability. O(n2) worst case is minor, we can use TreeMap ( which in java is implemented with red-black tree) to balance tree though.
    Thanks for sharing


  • 1

    Thanks @HoSi. Will definitely try using TreeMap to optimize the code.


  • 0

    Good solution! But can we really use balanced tree instead of this one? I mean we need keep the structure of the tree in the inserted order. If we convert it into balance tree, we could get wrong answer.


  • 0
    H

    good catch, that should be the problem


  • 0
    D

    great solution and very easy to follow and study


  • 2
    M

    Here is the solution but getting TLE . You know why, thats because headset.size() is O(N) surprisngly. SO we cant use this Treeset/Treemap

    public List<Integer> countSmaller(int[] nums) {
        	if(nums==null || nums.length==0)
        		return new ArrayList<Integer>();
        	List<Integer> l =new ArrayList<Integer>();
        	
        	TreeSet<Integer> s=new TreeSet<>();
        	s.add(nums[nums.length-1]);
        	l.add(0);
        	for( int i=nums.length-2;i>=0;i--){
        		SortedSet<Integer> s1=s.headSet(nums[i]);
        		l.add(s1.size());
        		s.add(nums[i]);
        		
        	}
        	Collections.reverse(l);
    		return l;
    }

  • 0
    M

    We don't need to keep the inserted order. Just build the tree from back of the array and sum up all passing node's count.


  • 0
    A

    @m_rao : these are arrays contain duplicates [5,2,1,6,1], i don't think treeset or treemap will serve the purpose.


  • 2
    R

    Great, here is my solution. much easier.

    public class Solution {
        public List<Integer> countSmaller(int[] nums) {
            int[] res = new int[nums.length];
            List<Integer> list = new ArrayList<>();
            for(int i = nums.length - 1; i >= 0; i--) {
                res[i] = insert(list, nums[i]);
            }
            list.clear();
            for(int i = 0 ; i < nums.length; i++) {
                list.add(res[i]);
            }
            return list;
        }
        
        // binary insert
        private int insert(List<Integer> list, int num) {
            int l = 0;
            int r = list.size() - 1;
            while(l <= r) {
                int mid = l + (r - l)/2;
                int M = list.get(mid);
                if(M >= num) {
                    r = mid - 1;
                }else if(M < num) {
                    l = mid + 1;
                }
            }
            list.add(l, num);
            return l;
        }
    }
    

  • 0
    A

    @rayszhangqq Insert is O(n) time, so it is still O(n^2) time complexity


Log in to reply
 

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