Count of Smaller Numbers After Self — Hard Problem & Solution

Given an array nums, return an array counts where counts[i] is the number of elements to the right of nums[i] that are strictly smaller than it.

Difficulty: Hard
Topics: Arrays, Divide and Conquer, Binary Indexed Tree
Asked at: Amazon, Google, Uber
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an array nums, return an array counts where counts[i] is the number of elements to the right of nums[i] that are strictly smaller than it.

Example 1

Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation: To the right of 5 sit 2 and 1; to the right of 2 sits 1; to the right of 6 sits 1; nothing follows 1.

Example 2

Input: nums = [-1,-1]
Output: [0,0]
Explanation: Equal values do not count — the comparison is strict.

Example 3

Input: nums = [3,2,1]
Output: [2,1,0]

Constraints

1 <= nums.length <= 100000
-1000 <= nums[i] <= 1000

How to solve Count of Smaller Numbers After Self

Process the array from right to left, maintaining a frequency table of everything already seen — which is exactly 'everything to the right'. The answer for the current element is the count of stored values strictly below it, a prefix sum a Fenwick tree serves in O(log V).

Approach

Offset every value by +1001 so the range [-1000, 1000] becomes [1, 2001]; a Fenwick tree is 1-indexed and would loop forever on index 0.
Sweep i from n - 1 down to 0. Query the prefix sum up to v - 1 — the number of stored values strictly less than v — and record it.
Insert v into the tree, then continue.
Reverse the collected answers, since they were produced right to left.

Why it works

When index i is processed, the tree holds precisely nums[i+1..n-1], so prefix(v - 1) counts exactly the elements to the right that are strictly smaller. Using v - 1 rather than v is what excludes ties.

Complexity

Time — O(n log V)
Space — O(V)

Pitfalls

Querying prefix(v) counts equal values too and overcounts every duplicate.
Forgetting the final reverse returns the answers back to front.
Merge sort with an index array is the other standard solution and has the same complexity.

Reference solution

Python

from typing import List

def countSmaller(nums: List[int]) -> List[int]:
    OFF, SIZE = 1001, 2002
    bit = [0] * (SIZE + 1)
    out = []
    for i in range(len(nums) - 1, -1, -1):
        v = nums[i] + OFF
        s = 0
        p = v - 1
        while p > 0:
            s += bit[p]
            p -= p & -p
        out.append(s)
        q = v
        while q <= SIZE:
            bit[q] += 1
            q += q & -q
    out.reverse()
    return out

JavaScript

var countSmaller = function(nums) {
    var OFF = 1001, SIZE = 2002;
    var bit = [];
    for (var t = 0; t <= SIZE; t++) bit.push(0);
    var out = [];
    for (var i = nums.length - 1; i >= 0; i--) {
        var v = nums[i] + OFF;
        var s = 0;
        for (var p = v - 1; p > 0; p -= p & -p) s += bit[p];
        out.push(s);
        for (var q = v; q <= SIZE; q += q & -q) bit[q]++;
    }
    out.reverse();
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue