Solution :: Count of smaller Number after self


  • 0
    X

    Solutions

    Approach #1 (Naive double loop) [Time Limit Exceeded]

    Java

    import java.util.Arrays;
    
    class Solution {
        public List<Integer> countSmaller(int[] nums) {
           Integer[] counts = new Integer[nums.length];
           for (int i = 0; i < nums.length; i++) {
               counts[i] = 0;
               for (int j = i + 1; j < nums.length; j++) {
                   if (nums[j] < nums[i]) {
                       counts[i] += 1;
                   }
               }
           }
           return Arrays.asList(counts);
        }
    }
    

    Complexity Analysis

    O(n^2)

    Approach #2 (Modified Binary Search Tree) [Accepted]

    Use a modified BST where each node keeps track of the number of nodes in the tree that have smaller values (number of left descendants). Let us call this extra field leftWeight.

    • Starting from the right-most value in the input array, recursively insert nodes to the BST. For every index i, the BST is guaranteed to only have values at indexes > i.
    • With every right-leaning move down the BST, keep track of the number of nodes that have values less than the current value.
    • Update leftWeight accordingly with every left-leaning move down the BST.

    Java

    import java.util.Arrays;
    
    class Solution {
        private class TreeNode {
            int val;
            TreeNode left;
            TreeNode right;
            int leftWeight;
            
            TreeNode(int val) {
                this.val = val;
            }
        }
        
        private Integer insertAndGetLessThanCount(TreeNode root, TreeNode node, int numLessThan) {
            if (node.val <= root.val) { // insert to left
                root.leftWeight += 1;
                if (root.left == null) {
                    root.left = node;
                    return numLessThan;
                } else {
                    return insertAndGetLessThanCount(root.left, node, numLessThan);
                }
            } else { // insert right
                numLessThan += root.leftWeight + 1;
                if (root.right == null) {
                    root.right = node;
                    return numLessThan;
                } else {
                    return insertAndGetLessThanCount(root.right, node, numLessThan);
                }
            }
        }
    
        public List<Integer> countSmaller(int[] nums) {
            Integer[] counts = new Integer[nums.length];
            if (counts.length > 0) {
                counts[nums.length-1] = 0;
                TreeNode root = new TreeNode(nums[nums.length-1]);
                for (int i = nums.length - 2; i >= 0; i--) {
                    TreeNode node = new TreeNode(nums[i]);
                    counts[i] = insertAndGetLessThanCount(root, node, 0);
                }
            }
            return Arrays.asList(counts);
        }
    }
    

    Complexity Analysis

    The time complexity of this approach is O(n * height of BST).

    For a balanced BST the time complexity is O(nlogn).

    For an extremly imbalanced BST the time complexity degrades to O(n^2).

    The imbalanced case can be avoided by using a self-balancing BST such 2-3 tree, AVL tree, etc.


Log in to reply
 

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