Count of Smaller Numbers After Self

Problem

Given an integer array nums, return an integer array counts where counts[i] is the number of smaller elements to the right of nums[i].

Examples

The brute-force approach

For each element, scan every element to its right and count how many are smaller.

counts = []
for i in range(len(nums)):
    count = 0
    for j in range(i+1, len(nums)):
        if nums[j] < nums[i]:
            count += 1
    counts.append(count)
return counts

O(n²) — for each of the n elements you scan up to n elements to the right.

Spotting the pattern

This is a Divide and Conquer problem. The key question to ask yourself:

During the merge step of merge sort, when you finally place a left-half element, what do the right-half elements you have already placed tell you about it?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.