# Count of Smaller Numbers After Self
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-of-smaller-numbers-after-self)
Canonical: https://scaleengineer.com/dsa/problems/count-of-smaller-numbers-after-self
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer), [Merge Sort](https://scaleengineer.com/algorithms/merge-sort)
**Data structures:** Array, Binary Indexed Tree, Segment Tree, Ordered Set
**Companies:** [Geico](https://scaleengineer.com/companies/geico)
---
## Problem
Given an integer array `nums`, return _an integer array_ `counts` _where_ `counts[i]` _is the number of smaller elements to the right of_ `nums[i]`.

**Example 1:**

**Input:** nums = [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.

**Example 2:**

**Input:** nums = [-1]
**Output:** [0]

**Example 3:**

**Input:** nums = [-1,-1]
**Output:** [0,0]

**Constraints:**

* `1 <= nums.length <= 105`
* `-104 <= nums[i] <= 104`

# Approaches
## Brute Force - Nested Loops
The most straightforward approach is to use nested loops. For each element at index i, we iterate through all elements to its right and count how many are smaller.
**Time:** O(n²) - We have nested loops where outer loop runs n times and inner loop runs up to n times · **Space:** O(1) - Only using constant extra space (not counting the result array)
**Pros:** Simple and easy to understand; No extra space needed except for result; Works correctly for all cases
**Cons:** Very slow for large inputs; Not scalable; Inefficient for the given constraints
### Explanation
For each element at position i, we iterate through all elements from position i+1 to the end of the array. We maintain a counter that increments whenever we find an element smaller than nums[i]. This counter becomes the result for position i.

```java
public List<Integer> countSmaller(int[] nums) {
    List<Integer> result = new ArrayList<>();
    
    for (int i = 0; i < nums.length; i++) {
        int count = 0;
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] < nums[i]) {
                count++;
            }
        }
        result.add(count);
    }
    
    return result;
}
```
### Algorithm
- Initialize an empty result list
- For each element at index i from 0 to n-1:
  - Initialize count = 0
  - For each element at index j from i+1 to n-1:
    - If nums[j] < nums[i], increment count
  - Add count to result list
- Return result list

## Merge Sort with Index Tracking
We can use a modified merge sort approach where we track the original indices and count inversions during the merge process. This leverages the divide and conquer paradigm.
**Time:** O(n log n) - Standard merge sort time complexity · **Space:** O(n) - Extra space for temporary arrays during merge
**Pros:** Much faster than brute force; Uses divide and conquer efficiently; Stable sorting maintains relative order
**Cons:** More complex implementation; Requires understanding of merge sort; Uses additional space for pairs and temporary arrays
### Explanation
We create pairs of (value, original_index) and sort them using merge sort. During the merge process, when we take an element from the right subarray, it means all remaining elements in the left subarray are greater than this element, so we update their counts accordingly.

```java
public List<Integer> countSmaller(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    int[][] pairs = new int[n][2];
    
    // Create pairs of (value, index)
    for (int i = 0; i < n; i++) {
        pairs[i][0] = nums[i];
        pairs[i][1] = i;
    }
    
    mergeSort(pairs, 0, n - 1, result);
    
    List<Integer> list = new ArrayList<>();
    for (int count : result) {
        list.add(count);
    }
    return list;
}

private void mergeSort(int[][] pairs, int left, int right, int[] result) {
    if (left >= right) return;
    
    int mid = left + (right - left) / 2;
    mergeSort(pairs, left, mid, result);
    mergeSort(pairs, mid + 1, right, result);
    merge(pairs, left, mid, right, result);
}

private void merge(int[][] pairs, int left, int mid, int right, int[] result) {
    int[][] temp = new int[right - left + 1][2];
    int i = left, j = mid + 1, k = 0;
    
    while (i <= mid && j <= right) {
        if (pairs[i][0] <= pairs[j][0]) {
            result[pairs[i][1]] += (right - j + 1);
            temp[k++] = pairs[i++];
        } else {
            temp[k++] = pairs[j++];
        }
    }
    
    while (i <= mid) {
        temp[k++] = pairs[i++];
    }
    while (j <= right) {
        temp[k++] = pairs[j++];
    }
    
    for (int p = 0; p < temp.length; p++) {
        pairs[left + p] = temp[p];
    }
}
```
### Algorithm
- Create pairs of (value, original_index)
- Apply merge sort on these pairs
- During merge process:
  - When taking element from left subarray, add count of remaining elements in right subarray
  - This count represents smaller elements to the right
- Return the accumulated counts for each original index

## Binary Indexed Tree (Fenwick Tree)
We can use a Binary Indexed Tree to efficiently count smaller elements. We process the array from right to left, and for each element, we query the BIT for count of smaller elements, then update the BIT with current element.
**Time:** O(n log n) - Each update and query operation takes O(log n) time, done n times · **Space:** O(n) - Space for BIT and coordinate compression maps
**Pros:** Efficient O(n log n) solution; Handles duplicates well; Good for range sum queries; Memory efficient with coordinate compression
**Cons:** Requires understanding of Binary Indexed Tree; Implementation is more complex; Coordinate compression adds complexity
### Explanation
Since the range of numbers is limited (-10^4 to 10^4), we can use coordinate compression and a Binary Indexed Tree. We process elements from right to left: for each element, we query how many smaller elements we've seen so far, then add the current element to our data structure.

```java
public List<Integer> countSmaller(int[] nums) {
    // Coordinate compression
    Set<Integer> set = new TreeSet<>();
    for (int num : nums) {
        set.add(num);
    }
    
    Map<Integer, Integer> map = new HashMap<>();
    int idx = 1;
    for (int num : set) {
        map.put(num, idx++);
    }
    
    int[] result = new int[nums.length];
    BIT bit = new BIT(set.size());
    
    // Process from right to left
    for (int i = nums.length - 1; i >= 0; i--) {
        int compressedVal = map.get(nums[i]);
        result[i] = bit.query(compressedVal - 1);
        bit.update(compressedVal, 1);
    }
    
    List<Integer> list = new ArrayList<>();
    for (int count : result) {
        list.add(count);
    }
    return list;
}

class BIT {
    private int[] tree;
    private int n;
    
    public BIT(int n) {
        this.n = n;
        this.tree = new int[n + 1];
    }
    
    public void update(int idx, int val) {
        for (int i = idx; i <= n; i += i & (-i)) {
            tree[i] += val;
        }
    }
    
    public int query(int idx) {
        int sum = 0;
        for (int i = idx; i > 0; i -= i & (-i)) {
            sum += tree[i];
        }
        return sum;
    }
}
```
### Algorithm
- Perform coordinate compression to map values to indices
- Initialize Binary Indexed Tree
- Process array from right to left:
  - Query BIT for count of elements smaller than current element
  - Update BIT with current element
  - Store the query result as count for current position
- Return the result array

## Balanced Binary Search Tree (TreeMap)
We can use a balanced BST (TreeMap in Java) to maintain a sorted collection of elements we've seen so far. For each element, we count smaller elements using the BST, then add the current element to the BST.
**Time:** O(n log n) - Each TreeMap operation takes O(log n) time, and we do this n times · **Space:** O(n) - Space for TreeMap to store unique elements and their frequencies
**Pros:** Uses built-in Java data structures; Relatively simple to implement; Automatically handles sorting; Good performance for most cases
**Cons:** May be slower than BIT due to overhead of TreeMap operations; Summing values in headMap can be expensive; Not as memory efficient as other approaches
### Explanation
We process the array from right to left, maintaining a TreeMap that stores the frequency of each element we've encountered. For each element, we use the headMap functionality to count all smaller elements, then add the current element to our TreeMap.

```java
public List<Integer> countSmaller(int[] nums) {
    int[] result = new int[nums.length];
    TreeMap<Integer, Integer> map = new TreeMap<>();
    
    // Process from right to left
    for (int i = nums.length - 1; i >= 0; i--) {
        // Count smaller elements
        int count = 0;
        for (Map.Entry<Integer, Integer> entry : map.headMap(nums[i]).entrySet()) {
            count += entry.getValue();
        }
        result[i] = count;
        
        // Add current element to map
        map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
    }
    
    List<Integer> list = new ArrayList<>();
    for (int c : result) {
        list.add(c);
    }
    return list;
}
```

Optimized version using TreeMap's built-in methods:

```java
public List<Integer> countSmaller(int[] nums) {
    int[] result = new int[nums.length];
    TreeMap<Integer, Integer> map = new TreeMap<>();
    
    for (int i = nums.length - 1; i >= 0; i--) {
        Integer smaller = map.lowerKey(nums[i]);
        if (smaller != null) {
            result[i] = map.headMap(nums[i]).values().stream().mapToInt(Integer::intValue).sum();
        }
        map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
    }
    
    List<Integer> list = new ArrayList<>();
    for (int c : result) {
        list.add(c);
    }
    return list;
}
```
### Algorithm
- Initialize empty TreeMap to store element frequencies
- Process array from right to left:
  - Use headMap to get all elements smaller than current element
  - Sum up their frequencies to get count of smaller elements
  - Add current element to TreeMap
  - Store count in result array
- Convert result array to list and return

# Solutions
### Java

```java
import java.util.ArrayList ; import java.util.Arrays ; import java.util.List ; public class Count_of_Smaller_Numbers_After_Self { public static void main ( String [] args ) { Count_of_Smaller_Numbers_After_Self out = new Count_of_Smaller_Numbers_After_Self (); Solution s = out . new Solution (); System . out . println ( s . countSmaller ( new int []{ 5 , 2 , 6 , 1 })); } class Solution { public List < Integer > countSmaller ( int [] nums ) { List < Integer > result = new ArrayList <>(); List < Integer > sorted = new ArrayList <>(); if ( nums == null || nums . length == 0 ) { return result ; } for ( int i = nums . length - 1 ; i >= 0 ; i --) { // binary search for current pos, reference: Arrays.binarySearch() int left = 0 ; int right = sorted . size (); while ( left < right ) { int mid = left + ( right - left ) / 2 ; if ( nums [ i ] <= sorted . get ( mid )) { right = mid ; } else { left = mid + 1 ; } } // now nums[i] should be placed at index left sorted . add ( left , nums [ i ]); // @note: equal to .insert() result . add ( 0 , left ); // @note: insert to 1st node，因为是倒序scan array } return result ; } } } ############ class Solution { public List < Integer > countSmaller ( int [] nums ) { Set < Integer > s = new HashSet <>(); for ( int v : nums ) { s . add ( v ); } List < Integer > alls = new ArrayList <>( s ); alls . sort ( Comparator . comparingInt ( a -> a )); int n = alls . size (); Map < Integer , Integer > m = new HashMap <>( n ); for ( int i = 0 ; i < n ; ++ i ) { m . put ( alls . get ( i ), i + 1 ); } BinaryIndexedTree tree = new BinaryIndexedTree ( n ); LinkedList < Integer > ans = new LinkedList <>(); for ( int i = nums . length - 1 ; i >= 0 ; -- i ) { int x = m . get ( nums [ i ]); tree . update ( x , 1 ); ans . addFirst ( tree . query ( x - 1 )); } return ans ; } } class BinaryIndexedTree { private int n ; private int [] c ; public BinaryIndexedTree ( int n ) { this . n = n ; c = new int [ n + 1 ]; } public void update ( int x , int delta ) { while ( x <= n ) { c [ x ] += delta ; x += lowbit ( x ); } } public int query ( int x ) { int s = 0 ; while ( x > 0 ) { s += c [ x ]; x -= lowbit ( x ); } return s ; } public static int lowbit ( int x ) { return x & - x ; } }
```

### Python

```python
''' bisect: maintaining a list in sorted order without having to sort the list after each insertion. https://docs.python.org/3/library/bisect.html bisect.bisect_left() Locate the insertion point for x in a to maintain sorted order. bisect.bisect_right() or bisect.bisect() Similar to bisect_left(), but returns an insertion point which comes after (to the right of) any existing entries of x in a. bisect.insort_left(a, x, lo=0, hi=len(a), *, key=None) Insert x in a in sorted order. Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step. bisect.insort_right(a, x, lo=0, hi=len(a), *, key=None) bisect.insort(a, x, lo=0, hi=len(a), *, key=None) Similar to insort_left(), but inserting x in a after any existing entries of x. >>> import bisect >>> bisect.bisect_left([1,2,3], 2) 1 >>> bisect.bisect_right([1,2,3], 2) 2 >>> a = [1, 1, 1, 2, 3] >>> bisect.insort_left(a, 1.0) >>> a [1.0, 1, 1, 1, 2, 3] >>> a = [1, 1, 1, 2, 3] >>> bisect.insort_right(a, 1.0) >>> a [1, 1, 1, 1.0, 2, 3] >>> a = [1, 1, 1, 2, 3] >>> bisect.insort(a, 1.0) >>> a [1, 1, 1, 1.0, 2, 3] ''' import bisect class Solution ( object ): def countSmaller ( self , nums ): """ :type nums: List[int] :rtype: List[int] """ ans = [] bst = [] for num in reversed ( nums ): idx = bisect . bisect_left ( bst , num ) ans . append ( idx ) bisect . insort ( bst , num ) return ans [:: - 1 ] ############ class BinaryIndexedTree : def __init__ ( self , n ): self . n = n self . c = [ 0 ] * ( n + 1 ) @ staticmethod def lowbit ( x ): return x & - x def update ( self , x , delta ): while x <= self . n : self . c [ x ] += delta x += BinaryIndexedTree . lowbit ( x ) def query ( self , x ): s = 0 while x > 0 : s += self . c [ x ] x -= BinaryIndexedTree . lowbit ( x ) return s class Solution : def countSmaller ( self , nums : List [ int ]) -> List [ int ]: alls = sorted ( set ( nums )) m = { v : i for i , v in enumerate ( alls , 1 )} tree = BinaryIndexedTree ( len ( m )) ans = [] for v in nums [:: - 1 ]: x = m [ v ] tree . update ( x , 1 ) ans . append ( tree . query ( x - 1 )) return ans [:: - 1 ]
```

### CPP

```cpp
// OJ: https://leetcode.com/problems/count-of-smaller-numbers-after-self/ // Time: O(NlogN) // Space: O(N) class Solution { vector < int > id , tmp , ans ; void solve ( vector < int > & A , int begin , int end ) { if ( begin + 1 >= end ) return ; int mid = ( begin + end ) / 2 , i = begin , j = mid , k = begin ; solve ( A , begin , mid ); solve ( A , mid , end ); for (; i < mid ; ++ i ) { while ( j < end && A [ id [ j ]] < A [ id [ i ]]) { tmp [ k ++ ] = id [ j ++ ]; } ans [ id [ i ]] += j - mid ; tmp [ k ++ ] = id [ i ]; } for (; j < end ; ++ j ) tmp [ k ++ ] = id [ j ]; for ( int i = begin ; i < end ; ++ i ) id [ i ] = tmp [ i ]; } public: vector < int > countSmaller ( vector < int >& A ) { int N = A . size (); id . assign ( N , 0 ); tmp . assign ( N , 0 ); ans . assign ( N , 0 ); iota ( begin ( id ), end ( id ), 0 ); solve ( A , 0 , N ); return ans ; } };
```