Count Smaller Numbers After Self — BIT and Merge Sort Guide

Problem Statement#

Given an integer 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 nums[i].

Constraints:

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

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

Input:  nums = [-1, -1]
Output: [0, 0]

Why This Problem Matters#

LeetCode 315 is a hard problem that shows up repeatedly in Google and Amazon binary search interview rounds. It bridges two algorithmic worlds: sorting-based inversion counting and tree-based prefix queries. Solving it well demonstrates that you can move between paradigms instead of memorizing one.

The deeper reason this problem matters is that counting smaller elements to the right is the same problem as counting inversions during sorting. Once you see this equivalence, you unlock augmented merge sort and Fenwick Tree techniques that apply to dozens of other interview problems. FAANG O(log n) interviews routinely follow up with reverse pairs or count of range sum, which require the same toolkit.

The Binary Indexed Tree route also doubles as an interview opportunity to talk about coordinate compression — a technique you must apply whenever value ranges are large or include negatives. Demonstrating both approaches shows depth.

The Core Insight#

Either traverse the array right-to-left while maintaining an order statistic structure (BIT keyed on compressed values), or sort the array and during the merge of two halves count how many elements from the right half are merged before each element of the left half. Both yield O(n log n) and both rely on a binary indexed structure.

Visual Dry Run#

Input [5, 2, 6, 1]. Walk right-to-left with a BIT over compressed ranks 1->1, 2->2, 5->3, 6->4.

Result reversed: [2, 1, 1, 0].

Solution (Optimal)#

class Solution:
    def countSmaller(self, nums):
        sorted_unique = sorted(set(nums))
        rank = {v: i + 1 for i, v in enumerate(sorted_unique)}
 
        n = len(sorted_unique)
        bit = [0] * (n + 1)
 
        def update(i):
            while i <= n:
                bit[i] += 1
                i += i & -i
 
        def query(i):
            s = 0
            while i > 0:
                s += bit[i]
                i -= i & -i
            return s
 
        result = [0] * len(nums)
        for i in range(len(nums) - 1, -1, -1):
            r = rank[nums[i]]
            result[i] = query(r - 1)
            update(r)
        return result

var countSmaller = function(nums) {
    const sorted = [...new Set(nums)].sort((a, b) => a - b);
    const rank = new Map();
    sorted.forEach((v, i) => rank.set(v, i + 1));
 
    const n = sorted.length;
    const bit = new Array(n + 1).fill(0);
 
    const update = (i) => {
        while (i <= n) { bit[i]++; i += i & -i; }
    };
    const query = (i) => {
        let s = 0;
        while (i > 0) { s += bit[i]; i -= i & -i; }
        return s;
    };
 
    const result = new Array(nums.length).fill(0);
    for (let i = nums.length - 1; i >= 0; i--) {
        const r = rank.get(nums[i]);
        result[i] = query(r - 1);
        update(r);
    }
    return result;
};

Time: O(n log n) — n insertions and queries each O(log n). Space: O(n) — BIT and rank map.

Common Mistakes#

• Forgetting coordinate compression and creating a BIT sized by raw value range, blowing memory.
• Using query(r) instead of query(r - 1), double-counting equal elements.
• Iterating left-to-right and querying suffix counts, which still works but is conceptually slipperier.
• Breaking on negative numbers when the BIT is 1-indexed but rank starts at 0.
• Allocating bit with size n instead of n + 1, causing index-out-of-bounds.

Interview Tips#

• State both approaches first — merge sort and BIT — and pick BIT for clarity.
• Always mention coordinate compression explicitly.
• Walk the BIT update/query loop with a tiny example so the interviewer sees you understand i & -i.

Follow-up Questions#

• How would you solve this with merge sort? Track original indices and count cross-pair inversions.
• What if values were doubles? Compress to ranks; the algorithm is unchanged.
• Can you do it online as elements arrive? Use an order statistic tree (e.g. SortedList) for O(log n) per insert and rank.
• Reverse pairs (LC 493) and count of range sum (LC 327) build on this — derive both.
• What if the array were 2D and you wanted counts in a quadrant? CDQ divide and conquer.

Key Takeaways#

• LC 315 reduces to inversion counting under a strict-less comparator.
• A Fenwick Tree over compressed ranks gives clean O(n log n) with O(n) memory.
• Always traverse right-to-left and query strictly smaller ranks (r - 1).
• Coordinate compression is mandatory whenever values are large or negative.
• Augmented merge sort is the alternative — count cross inversions during merge.
• The same toolkit solves LC 327 and LC 493.
• BIT update and query are 1-indexed; size the array n + 1.