315. Count of Smaller Numbers After Self

Source link: https://leetcode.com/problems/count-of-smaller-numbers-after-self/

Design

https://leetcode.com/problems/count-of-smaller-numbers-after-self/discuss/507591/Simple-Binary-Search-solution

Implementation

class Solution {
  public List<Integer> countSmaller(int[] nums) {
    int n = nums.length;
    List<Integer> sortedList = new ArrayList<>();
    Integer[] res = new Integer[n];
    for (int i = n - 1; i >= 0; i--) {
      // Find the position to insert
      int left = 0, right = sortedList.size();
      while(left < right) {
        int mid = left + (right - left) / 2;
        if (sortedList.get(mid) >= nums[i])
          right = mid;
        else 
          left = mid + 1;
      }
      res[i] = right;
            // O(n) time complexity
      sortedList.add(right, nums[i]);
    }
    return Arrays.asList(res);
  }
}

Complexity Analysis

Time: $O(n^2)$

Space: $O(n)$