Problem 36.2 · Advanced Data StructuresHard

Count of Smaller Numbers After Self

PatternRange Queries (Fenwick & Segment Trees)Divide and Conquer

What it teaches: Scan from the right, counting with a Fenwick tree over (compressed) values.

Practise it on judges as “Count of Smaller Numbers After Self”.

In plain words

For each number, count how many smaller numbers sit to its right. Sort the list with merge sort while remembering where each number came from. Whenever a number from the right half jumps ahead of a number from the left half, it was smaller and to its right, so count it.

Return the counts. Example: nums = [5, 2, 6, 1] → [2, 1, 1, 0].

The problem

For each element, count how many elements to its right are smaller. Return the counts.

Example 1

Input: nums = [5, 2, 6, 1]
Output: [2, 1, 1, 0]

Constraints

1 ≤ n ≤ 10⁵
−10⁴ ≤ nums[i] ≤ 10⁴

Pattern clues in the wording

→ "Smaller to the right"
→ Count over values seen so far

These clues point to Range Queries (Fenwick & Segment Trees): Answer sums, minimums or counts over any range while the array keeps changing, in O(log n) per query and update.

Stuck? Take one hint at a time

Solution · starter

import java.util.*;

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        return new ArrayList<>();
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	nums = [5,2,6,1]	[2,1,1,0]
2	nums = [-1]	[0]
3	nums = [-1,-1]	[0,0]

From slow to fast

Approaches

1. Fenwick over values · O(n log V)2. Merge sort with indices · O(n log n)

Fenwick over values

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

From right to left: answer = prefix(value − 1); then add 1 at value.

Approach 1

import java.util.*;

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        int offset = 10001, size = 20003;
        int[] bit = new int[size + 1];
        Integer[] out = new Integer[nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            int v = nums[i] + offset;                 // 1..20001
            int count = 0;
            for (int j = v - 1; j > 0; j -= j & -j) count += bit[j];
            out[i] = count;
            for (int j = v; j <= size; j += j & -j) bit[j]++;
        }
        return Arrays.asList(out);
    }
}

Verdict: Values are small, so no compression needed.

Merge sort with indices

Time O(n log n) Space O(n)

Sort indices by value with merge sort; when taking an element from the left half, every element already taken from the right half is smaller and was to its right.

▶ Dry run: Merge sort counts right-side jumpsnums = [5, 2, 6, 1]

count(map)

5: 02: 06: 01: 0

Step 1/4Split into [5, 2] and [6, 1].

Approach 2

import java.util.*;

class Solution {
    private int[] count, idx, tmp;
    private int[] nums;

    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        this.nums = nums;
        count = new int[n];
        idx = new int[n];
        tmp = new int[n];
        for (int i = 0; i < n; i++) idx[i] = i;
        sort(0, n - 1);
        List<Integer> out = new ArrayList<>();
        for (int c : count) out.add(c);
        return out;
    }

    private void sort(int lo, int hi) {
        if (lo >= hi) return;
        int mid = (lo + hi) >>> 1;
        sort(lo, mid);
        sort(mid + 1, hi);
        int i = lo, j = mid + 1, k = lo, rightTaken = 0;
        while (i <= mid || j <= hi) {
            if (j > hi || (i <= mid && nums[idx[i]] <= nums[idx[j]])) {
                count[idx[i]] += rightTaken;
                tmp[k++] = idx[i++];
            } else {
                rightTaken++;
                tmp[k++] = idx[j++];
            }
        }
        for (k = lo; k <= hi; k++) idx[k] = tmp[k];
    }
}

Verdict: Works for any value range without compression.

Before you submit

Edge cases and common mistakes

Test these inputs

Duplicates (not counted as smaller)
Negative values

Mistakes people make

Counting equal values as smaller.

Interview

Follow-up questions

How is this related to counting inversions?

Command Palette