# 0315. Count of Smaller Numbers After Self

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

## Description

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:**

```
**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`

## ac1: Merge sort

Amazing solution from [https://leetcode.com/problems/count-of-smaller-numbers-after-self/discuss/445769/merge-sort-CLEAR-simple-EXPLANATION-with-EXAMPLES-O(n-lg-n](https://leetcode.com/problems/count-of-smaller-numbers-after-self/discuss/445769/merge-sort-CLEAR-simple-EXPLANATION-with-EXAMPLES-O\(n-lg-n)). So easy to understand that not like a hard problem.

```java
// Wrapper class for each and every value of the input array,
// to store the original index position of each value, before we merge sort the array
private class ArrayValWithOrigIdx {
    int val;
    int originalIdx;

    public ArrayValWithOrigIdx(int val, int originalIdx) {
        this.val = val;
        this.originalIdx = originalIdx;
    }
}

public List<Integer> countSmaller(int[] nums) {
    if (nums == null || nums.length == 0) return new LinkedList<Integer>();
    int n = nums.length;
    int[] result = new int[n];

    ArrayValWithOrigIdx[] newNums = new ArrayValWithOrigIdx[n];
    for (int i = 0; i < n; ++i) newNums[i] = new ArrayValWithOrigIdx(nums[i], i);

    mergeSortAndCount(newNums, 0, n - 1, result);

    // notice we don't care about the sorted array after merge sort finishes.
    // we only wanted the result counts, generated by running merge sort
    List<Integer> resultList = new LinkedList<Integer>();
    for (int i : result) resultList.add(i);
    return resultList;
}

private void mergeSortAndCount(ArrayValWithOrigIdx[] nums, int start, int end, int[] result) {
    if (start >= end) return;

    int mid = (start + end) / 2;
    mergeSortAndCount(nums, start, mid, result);
    mergeSortAndCount(nums, mid + 1, end, result);

    // left subarray start...mid
    // right subarray mid+1...end
    int leftPos = start;
    int rightPos = mid + 1;
    LinkedList<ArrayValWithOrigIdx> merged = new LinkedList<ArrayValWithOrigIdx>();
    int numElemsRightArrayLessThanLeftArray = 0;
    while (leftPos < mid + 1 && rightPos <= end) {
        if (nums[leftPos].val > nums[rightPos].val) {
            // this code block is exactly what the problem is asking us for:
            // a number from the right side of the original input array, is smaller
            // than a number from the left side
            //
            // within this code block,
            // nums[rightPos] is smaller than the start of the left sub-array.
            // Since left sub-array is already sorted,
            // nums[rightPos] must also be smaller than the entire remaining left sub-array
            ++numElemsRightArrayLessThanLeftArray;

            // continue with normal merge sort, merge
            merged.add(nums[rightPos]);
            ++rightPos;
        } else {
            // a number from left side of array, is smaller than a number from
            // right side of array
            result[nums[leftPos].originalIdx] += numElemsRightArrayLessThanLeftArray;

            // Continue with normal merge sort
            merged.add(nums[leftPos]);
            ++leftPos;
        }
    }

    // part of normal merge sort, if either left or right sub-array is not empty,
    // move all remaining elements into merged result
    while (leftPos < mid + 1) {
        result[nums[leftPos].originalIdx] += numElemsRightArrayLessThanLeftArray;

        merged.add(nums[leftPos]);
        ++leftPos;
    }
    while (rightPos <= end) {
        merged.add(nums[rightPos]);
        ++rightPos;
    }

    // part of normal merge sort
    // copy back merged result into array
    int pos = start;
    for (ArrayValWithOrigIdx m : merged) {
        nums[pos] = m;
        ++pos;
    }
}
```

## ac2: BST

This is not optimal, the worse case is still O(n^2), which is same as brute force.

```java
class Solution {
    public List<Integer> countSmaller(int[] nums) {
        LinkedList<Integer> res = new LinkedList<Integer>();
        // edge cases
        if (nums == null || nums.length == 0) return res;

        // iterate right to left, build tree, get result
        Node root = null;
        for (int i = nums.length - 1; i >= 0; i--) {
            root = getLessInsert(root, nums[i], 0, res);
        }
        Collections.reverse(res);

        return res;
    }
    private Node getLessInsert(Node root, int val, int prevSum, List<Integer> res) {
        if (root == null) {
            root = new Node(val);
            res.add(prevSum);
        } else if (val == root.val) {
            root.count++;
            res.add(root.leftSum + prevSum);
        } else if (val < root.val) {
            root.leftSum++;
            root.left = getLessInsert(root.left, val, prevSum, res);
        } else {  // val > root.val
            root.right = getLessInsert(root.right, val, prevSum + root.count + root.leftSum, res);
        }

        return root;
    }

    class Node {
        int val, leftSum, count;
        Node left, right;
        public Node(int val) {
            this.val = val;
            leftSum = 0;
            count = 1;
        }
    }
}

/*
BS
BST
BIT
merge sort
*/
```

## ac3: BIT

Binary Indexed Tree, O(nlogn) time gurantee.

```java
class Solution {
    public List<Integer> countSmaller(int[] nums) {
        LinkedList<Integer> res = new LinkedList<Integer>();
        // edge cases
        if (nums == null || nums.length == 0) return res;

        int[] nums2 = nums.clone();
        Arrays.sort(nums2);
        Map<Integer, Integer> rankMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums2.length; i++) {
            if (!rankMap.containsKey(nums2[i])) {
                rankMap.put(nums2[i], i+1);
            }
        }

        // BIT
        int[] tree = new int[nums.length + 1];
        for (int i = nums.length - 1; i >= 0; i--) {
            int rank = rankMap.get(nums[i]);
            res.add(sum(rank-1, tree));
            update(rank, tree);
        }
        Collections.reverse(res);

        return res;
    }

    private int sum(int n, int[] tree) {
        int res = 0;
        while (n > 0) {
            res += tree[n];
            n -= n & (-n);
        }
        return res;
    }
    private void update(int n, int[] tree) {
        while (n < tree.length) {
            tree[n]++;
            n += n & (-n);
        }
    }
}
/*
From right to left, for a num, I need to know how many smaller numbers we had met. So we use BIT to keep track of it. 
Smaller number means: num with lower rank. How to update BIT? For each num, we update BIT by doing rank+1.
*/
```
