LeetCode #315 Hard

Count of Smaller Numbers After Self

For every array position, count later elements whose values are smaller.

arraymerge-sortdivide-and-conquer

02

Intuition

Scanning the suffix for every index is direct but quadratic. During merge sort, the left and right halves preserve original ordering: every item in the right half originally appeared after every item in the left half. When a right value moves ahead of a left value during merging, it is a smaller later element for that left value. Carry original indices so these crossing counts are added to the correct answers.

How to spot this pattern

A per-index question about later elements often becomes a crossing-pair count. If relationships can be counted while two sorted halves merge, indexed merge sort gives O(n log n) time.

03

Approach

1

Attach each value to its original position

Build pairs (value, index) before sorting. Values may move during merge sort, but the index lets every accumulated count update the corresponding output slot.

2

Count right-half elements that cross during merge

While merging, choose the right pair when its value is strictly smaller and increment moved_right. Whenever a left pair is emitted, add moved_right because precisely those right-half elements have crossed ahead of it.

3

Merge equal values without counting them

Choose from the left when values are equal because the problem asks for strictly smaller values. Recursively count crossings inside both halves, then count crossings between them, covering every ordered pair exactly once.

04

Solution

▶1class Solution:
▶2    def countSmaller(self, nums: List[int]) -> List[int]:
▶3        answer = [0] * len(nums)
▶4        pairs = [(value, i) for i, value in enumerate(nums)]
▶5 
▶6        def sort(items):
▶7            if len(items) <= 1:
▶8                return items
▶9            middle = len(items) // 2
▶10            left = sort(items[:middle])
▶11            right = sort(items[middle:])
▶12            merged = []
▶13            i = 0
▶14            j = 0
▶15            moved_right = 0
▶16            while i < len(left) and j < len(right):
▶17                if right[j][0] < left[i][0]:
▶18                    merged.append(right[j])
▶19                    j += 1
▶20                    moved_right += 1
▶21                else:
▶22                    answer[left[i][1]] += moved_right
▶23                    merged.append(left[i])
▶24                    i += 1
▶25            while i < len(left):
▶26                answer[left[i][1]] += moved_right
▶27                merged.append(left[i])
▶28                i += 1
▶29            merged.extend(right[j:])
▶30            return merged
▶31 
▶32        sort(pairs)
▶33        return answer

05

Common pitfalls

Counting equal values as smaller

✗ Wrong

if right[j][0] <= left[i][0]:

✓ Right

if right[j][0] < left[i][0]:

The requested relation is strictly smaller, not smaller or equal.

Losing original positions

✗ Wrong

pairs = sorted(nums)

✓ Right

pairs = [(value, i) for i, value in enumerate(nums)]

Counts must be written back in input order after values move.

Adding all right elements

✗ Wrong

answer[left[i][1]] += len(right)

✓ Right

answer[left[i][1]] += moved_right

Only right elements already moved ahead are proven smaller than the current left value.

06

Edge cases

All values are equal

Equality selects the left element, so no false smaller counts are added.

Strictly decreasing input

Each left-side item accumulates all smaller items to its right across merge levels.

Negative and duplicate values

Comparisons use actual integer values and original indices, so both are handled naturally.

07

Complexity

Time

O(n log n)

Space

O(n)

Merge sort counts each cross-half relationship while maintaining auxiliary arrays.