Count of Smaller Numbers After Self

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:

  1. Given nums = [5, 2, 6, 1]
  3. To the right of 5 there are 2 smaller elements (2 and 1).
  4. To the right of 2 there is only 1 smaller element (1).
  5. To the right of 6 there is 1 smaller element (1).
  6. To the right of 1 there is 0 smaller element.

Return the array [2, 1, 1, 0].

Solution:

  1. public class Solution {
  2.   private void add(int[] bit, int i, int val) {
  3.     for (; i < bit.length; i += i & -i) bit[i] += val;
  4.   }
  6.   private int query(int[] bit, int i) {
  7.     int ans = 0;
  8.     for (; i > 0; i -= i & -i) ans += bit[i];
  9.     return ans;
  10.   }
  12.   public List<Integer> countSmaller(int[] nums) {
  13.     int[] tmp = nums.clone();
  14.     Arrays.sort(tmp);
  15.     for (int i = 0; i < nums.length; i++) nums[i] = Arrays.binarySearch(tmp, nums[i]) + 1;
  16.     int[] bit = new int[nums.length + 1];
  17.     Integer[] ans = new Integer[nums.length];
  18.     for (int i = nums.length - 1; i >= 0; i--) {
  19.       ans[i] = query(bit, nums[i] - 1);
  20.       add(bit, nums[i], 1);
  21.     }
  22.     return Arrays.asList(ans);
  23.   }
  24. }