Easiest Java solution


  • 47

    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


  • 0
    P

    Python translation:

    class node:
        def __init__(self,val):
            self.val = val
            self.left = None
            self.right = None
            self.count = 1
            
    class Solution(object):
        def countSmaller(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            if not nums:
                return []
            root = node(nums[-1])
            res = [0]
            
            for i in xrange(len(nums)-2,-1,-1):
                res.append(self.insert_node(nums[i],root))
            
            return res[::-1]
                
                
                
        def insert_node(self,val,root):
            count = 0
            
            while True:
                if val<=root.val:
                    root.count += 1 
                    if not root.left:
                        root.left = node(val)
                        break
                    root = root.left
                else:
                    count += root.count
                    if not root.right:
                        root.right = node(val)
                        break
                    root = root.right
            return count
                    
    

  • 0
    C

    thank you, nice and clean.


  • 0
    M

    Great solution! Using reverse seems to improve run time for leetcode's test cases, but for readability and from interview prospective I think using LinkedList and addFirst is better.
    FYI LinkedList and addFirst version run time is 12ms, not that big of the difference.


Log in to reply
 

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