> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0315-count-of-smaller-numbers-after-self.md).

# 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%28n-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.
*/
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jaywin.gitbook.io/leetcode/solutions/0315-count-of-smaller-numbers-after-self.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.