315. Count of Smaller Numbers After Self.md

315. Count of Smaller Numbers After Self

Question

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Input: [5,2,6,1]
Output: [2,1,1,0] 
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Thinking:

• Method 1: Slow, beats 18.69%

  • find the right closed index whose value is same as current one.
  • only need to calculate the value between these two and add the result of that index.

  class Solution {
      public List<Integer> countSmaller(int[] nums) {
          Map<Integer, Integer> map = new HashMap<>();
          int[] arr = new int[nums.length];
          for(int i = nums.length - 1; i>= 0; i--){
              if(map.containsKey(nums[i])){
                  arr[i] = map.get(nums[i]);
              }
              else{
                  arr[i] = -1;
              }
              map.put(nums[i], i);
          }
          int[] result = new int[nums.length];
          for(int i = nums.length - 1; i >= 0; i--){
              int count = 0;
              if(arr[i] == -1){
                  for(int j = i; j < nums.length; j++){
                      if(nums[i] > nums[j]) count++;
                  }
                  result[i] = count;
              }else{
                  for(int j = i; j < arr[i]; j++){
                      if(nums[i] > nums[j]) count++;
                  }
                  result[i] = count + result[arr[i]];
              }
          }
          List<Integer> res = new LinkedList<>();
          for(int n : result) res.add(n);
          return res;
      }
  }

• Method 2: Use index and frequency array. slow, beats 6.23%

  • Example[5,6,2,1]
    • We sort the array in ascending order[1,2,5,6]
    • we use another map to save the corresponding index: [2, 3, 1, 0], we need to remove the duplicate values.
    • we traversal the array from the end to the beginning, once we meet a value, we add the frequency.
    • Then we sum the appear number from the end to current index.

   class Solution {
       public List<Integer> countSmaller(int[] nums) {
           LinkedList<Integer> result = new LinkedList<>();
           if(nums == null || nums.length == 0) return result;
           Map<Integer, Integer> map = new HashMap<>();
           int[] copy = Arrays.copyOf(nums, nums.length);
           Arrays.sort(nums);
           int count = 0;
           map.put(nums[nums.length - 1], count);
           for(int i = nums.length - 2; i >= 0; i--){
               if(nums[i] != nums[i + 1]){
                   map.put(nums[i], ++count);
               }
           }
           int[] freq = new int[count+1];
           for(int i = copy.length - 1; i >= 0; i--){
               freq[map.get(copy[i])]++;
               int appear = 0;
               for(int j = count; j > map.get(copy[i]); j--){
                   appear += freq[j];
               }
               result.addFirst(appear);
           }
           return result;
       }
   }

  • Method 3: BST, Beats 99.02%
    • We create a Node and look into this node:

       private static class Node{
       int val;
       int count; // Number of current value.
       int leftCount;	// Number of left child Node for current node.
       Node left, right;
       public Node(int val){
           this.val = val;
           this.count = 1;
       }

    } ```
    • For a right child node, the number of values smaller than current value should be: node.leftCount + parent.count+ parent.leftCount, so here are three conditions:
      1. given value equals to node.val: we need to add node.count: node.count++;
      2. given value is smaller than current value:
         • left is null, create a new node and return 0
         • left is not null, return insert(node.left, val), means we recursively call the function.
      3. given value is bigger than current value:
         • right is null, create a new node and should return node.count + node.leftCount.
         • right is not null, return node.count + node.leftcount + insert(node.right, val).

     class Solution {
         private static class Node{
             int val;
             int count;
             int leftCount;
             Node left, right;
             public Node(int val){
                 this.val = val;
                 this.count = 1;
             }
         }
         public List<Integer> countSmaller(int[] nums) {
             LinkedList<Integer> result = new LinkedList<>();
             if(nums == null || nums.length == 0) return result;
             Node root = new Node(nums[nums.length - 1]);
             result.add(0);
             for(int i = nums.length - 2; i >= 0; i--){
                 result.addFirst(insert(root, nums[i]));
             }
             return result;
         }
         private int insert(Node node, int val){        
             if(val == node.val){
                 node.count ++;
                 return node.leftCount;
             }else if(val < node.val){
                 node.leftCount++;
                 if(node.left == null){
                     node.left = new Node(val);
                     return 0;
                 }else{
                     return insert(node.left, val);
                 }
             }else{
                 if(node.right == null){
                     node.right = new Node(val);
                     return node.count + node.leftCount;
                 }else return node.count + node.leftCount + insert(node.right, val);
             }
         }
     }