# LeetCode 315: Count of Smaller Numbers After Self

## Problem Restatement

We are given an integer array `nums`.

For each index `i`, count how many numbers to the right of `nums[i]` are smaller than `nums[i]`.

Return an array `counts`, where:

```python
counts[i] = number of smaller elements to the right of nums[i]
```

For example, in:

```python
nums = [5, 2, 6, 1]
```

the answer is:

```python
[2, 1, 1, 0]
```

because:

| Index | Value | Smaller values to the right | Count |
|---:|---:|---|---:|
| `0` | `5` | `2, 1` | `2` |
| `1` | `2` | `1` | `1` |
| `2` | `6` | `1` | `1` |
| `3` | `1` | none | `0` |

The official constraints include `1 <= nums.length <= 10^5` and `-10^4 <= nums[i] <= 10^4`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Output | Integer array `counts` |
| `counts[i]` | Number of elements smaller than `nums[i]` to its right |
| Important detail | Equal numbers are not smaller |
| Target | Efficient solution for large `n` |

Function shape:

```python
def countSmaller(nums: list[int]) -> list[int]:
    ...
```

## Examples

Example 1:

```python
nums = [5, 2, 6, 1]
```

Output:

```python
[2, 1, 1, 0]
```

Example 2:

```python
nums = [-1]
```

Output:

```python
[0]
```

There is no number to the right.

Example 3:

```python
nums = [-1, -1]
```

Output:

```python
[0, 0]
```

The second `-1` is equal to the first `-1`, not smaller.

## First Thought: Compare Every Pair

The simplest method is:

1. For every index `i`.
2. Scan every index `j > i`.
3. Count values where `nums[j] < nums[i]`.

Code idea:

```python
for i in range(n):
    for j in range(i + 1, n):
        if nums[j] < nums[i]:
            counts[i] += 1
```

This is correct.

But it costs:

```python
O(n^2)
```

With `n` up to `100000`, this is too slow.

## Key Insight

Process the array from right to left.

When we stand at index `i`, all numbers to the right have already been seen.

So the problem becomes:

> Among the seen numbers, how many are smaller than `nums[i]`?

We need a data structure that supports:

| Operation | Meaning |
|---|---|
| Add one number | Mark that this value has appeared on the right |
| Count smaller numbers | Count how many seen values are less than current value |

A Fenwick Tree can do this efficiently if values are mapped into compact integer ranks.

## Coordinate Compression

Fenwick Tree uses positive indices.

But `nums` may contain negative values.

So we compress values into ranks.

For example:

```python
nums = [5, 2, 6, 1]
```

Sorted unique values:

```python
[1, 2, 5, 6]
```

Ranks:

| Value | Rank |
|---:|---:|
| `1` | `1` |
| `2` | `2` |
| `5` | `3` |
| `6` | `4` |

Now “values smaller than `5`” means “ranks less than `3`”.

That can be queried as a prefix sum.

## Fenwick Tree Meaning

The Fenwick Tree stores frequencies.

If we have already seen values on the right, then:

```python
tree rank r = how many times value with rank r has appeared
```

To count numbers smaller than current value:

```python
rank = value_to_rank[nums[i]]
answer[i] = tree.query(rank - 1)
```

We query `rank - 1` because equal values are not smaller.

Then we add the current value into the tree:

```python
tree.add(rank, 1)
```

## Algorithm

1. Sort all unique values in `nums`.
2. Map each value to rank starting from `1`.
3. Create a Fenwick Tree.
4. Create result array `counts`.
5. Iterate from right to left:
   - Get rank of `nums[i]`.
   - Query how many seen numbers have smaller rank.
   - Store that count in `counts[i]`.
   - Add current rank to the Fenwick Tree.
6. Return `counts`.

## Correctness

When the algorithm processes index `i`, it has already inserted exactly the elements to the right of `i` into the Fenwick Tree.

The Fenwick Tree stores frequencies by rank. Since coordinate compression preserves order, a value is smaller than `nums[i]` exactly when its rank is less than `rank(nums[i])`.

The query:

```python
tree.query(rank - 1)
```

returns the total frequency of all seen values with smaller rank. These are exactly the elements to the right of `i` that are smaller than `nums[i]`.

After storing this count, the algorithm inserts `nums[i]` into the tree, so it becomes available for indices further left.

Therefore, every `counts[i]` is computed correctly.

## Complexity

Let `n = len(nums)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n log n)` | Sorting unique values plus one Fenwick query and update per element |
| Space | `O(n)` | Rank map, Fenwick Tree, and answer array |

## Implementation

```python
class FenwickTree:

    def __init__(self, size: int):
        self.n = size
        self.tree = [0] * (size + 1)

    def add(self, index: int, delta: int) -> None:
        while index <= self.n:
            self.tree[index] += delta
            index += index & -index

    def query(self, index: int) -> int:
        total = 0

        while index > 0:
            total += self.tree[index]
            index -= index & -index

        return total

class Solution:
    def countSmaller(self, nums: list[int]) -> list[int]:
        sorted_values = sorted(set(nums))

        value_to_rank = {
            value: rank
            for rank, value in enumerate(sorted_values, start=1)
        }

        bit = FenwickTree(len(sorted_values))
        counts = [0] * len(nums)

        for i in range(len(nums) - 1, -1, -1):
            rank = value_to_rank[nums[i]]

            counts[i] = bit.query(rank - 1)

            bit.add(rank, 1)

        return counts
```

## Code Explanation

First, collect sorted unique values:

```python
sorted_values = sorted(set(nums))
```

Then map each value to a compact rank:

```python
value_to_rank = {
    value: rank
    for rank, value in enumerate(sorted_values, start=1)
}
```

Ranks start at `1` because Fenwick Tree uses 1-based indexing.

Create the tree and answer array:

```python
bit = FenwickTree(len(sorted_values))
counts = [0] * len(nums)
```

Now scan from right to left:

```python
for i in range(len(nums) - 1, -1, -1):
```

Get the current value's rank:

```python
rank = value_to_rank[nums[i]]
```

Count seen values with smaller rank:

```python
counts[i] = bit.query(rank - 1)
```

Then insert the current number into the seen set:

```python
bit.add(rank, 1)
```

The Fenwick Tree methods are standard.

`add` updates all frequency buckets affected by one rank.

```python
index += index & -index
```

`query` sums frequencies from rank `1` through `index`.

```python
index -= index & -index
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.countSmaller([5, 2, 6, 1]) == [2, 1, 1, 0]
    assert s.countSmaller([-1]) == [0]
    assert s.countSmaller([-1, -1]) == [0, 0]
    assert s.countSmaller([1, 2, 3, 4]) == [0, 0, 0, 0]
    assert s.countSmaller([4, 3, 2, 1]) == [3, 2, 1, 0]
    assert s.countSmaller([2, 0, 1, 2, 1]) == [3, 0, 0, 1, 0]
    assert s.countSmaller([0, -1, -1, 2]) == [2, 0, 0, 0]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[5, 2, 6, 1]` | Standard example |
| `[-1]` | Single element |
| `[-1, -1]` | Equal values are not smaller |
| Increasing array | All counts are zero |
| Decreasing array | Every later value is smaller |
| Duplicates | Confirms strict smaller logic |
| Negative values | Confirms coordinate compression |