Count Smaller Numbers

For each element, count how many numbers to its right are smaller.

arrays counting merge-sort sorting

Write a function `count_smaller(nums)` that takes a list of integers `nums` and returns a list of integers where the value at index `i` is the count of numbers to the right of `i` that are strictly smaller than `nums[i]`.

For example, for `nums = [5, 2, 6, 1]`:
- At index 0, `5` has two smaller numbers to its right: `2` and `1` → 2.
- At index 1, `2` has one smaller number to its right: `1` → 1.
- At index 2, `6` has one smaller number to its right: `1` → 1.
- At index 3, `1` has none → 0.

Return `[2, 1, 1, 0]`.

Note: The input list can contain duplicates, and the function must handle negative numbers as well.

Constraints

- `0 <= len(nums) <= 10^5`
- `-10^4 <= nums[i] <= 10^4`
- The expected time complexity is `O(n log n)`, but a correct `O(n^2)` solution may pass if the test set is small.
- The function should not modify the original list.

Example

```python
>>> count_smaller([5, 2, 6, 1])
[2, 1, 1, 0]
>>> count_smaller([-1, -1])
[0, 0]
>>> count_smaller([])
[]
>>> count_smaller([3, 2, 1])
[2, 1, 0]
```

20 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about a divide-and-conquer approach: split the list in half, solve each half, and count when merging.

When merging, if the left element is greater than a right element, it is greater than all remaining right elements in that block.

Alternatively, you could use a Fenwick tree (binary indexed tree) over the value range.

Duplicates are tricky: only count strictly smaller numbers, so be careful when comparing equal values.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.