Count of Smaller Numbers After Self — BIT, Fenwick Tree & Coordinate Compression Explained

Problem Statement#

LeetCode 315 — Count of Smaller Numbers After Self | Difficulty: Hard

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

Constraints:

• 1 is less than or equal to nums.length, which is less than or equal to 10^5
• -10^4 is less than or equal to nums[i], which is less than or equal to 10^4

Example 1:

Input:  nums = [5, 2, 6, 1]
Output: [2, 1, 1, 0]
Explanation:
  To the right of 5 there are 2 smaller elements (2 and 1)
  To the right of 2 there is 1 smaller element (1)
  To the right of 6 there is 1 smaller element (1)
  To the right of 1 there are 0 smaller elements

Example 2:

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

Why This Problem Matters#

This is the canonical interview question for Binary Indexed Trees (BIT) / Fenwick Trees combined with coordinate compression. Google, Amazon, Meta, and Bloomberg all rotate this problem because it tests three independent skills at once: spotting that a sweep from right to left turns "future smaller" into "already-seen smaller", picking the right data structure for dynamic frequency queries, and handling integer ranges that exceed array indices.

A naive double loop is O(n^2) and times out on the upper constraint of 10^5. The interviewer wants to see you reach for either a Fenwick Tree, a Segment Tree, a modified merge sort, or an Order-Statistics Tree. Of these, the BIT plus coordinate compression solution is the most concise and the most commonly expected. Once you understand it, every "count inversions / count pairs" variant — Reverse Pairs, Count of Range Sum, Number of Smaller Elements in a Sliding Window — becomes a small twist on the same scaffold.

The Core Insight#

The trick that turns this from O(n^2) into O(n log n) is a change of perspective combined with a frequency Fenwick Tree.

Insight 1: Sweep right to left. Walk the array from the last index backward. At index i, every element you have already inserted is one of the elements "to the right of i". So the question reduces to: how many of the already-inserted values are strictly less than nums[i]?

Insight 2: Replace values with ranks. The raw values can be anywhere in the range minus 10^4 to plus 10^4 — too sparse to index directly. Sort the unique values, assign rank 1, 2, 3 ... and replace each nums[i] with its rank. Now every value lives in the dense range from 1 to n, perfect for a Fenwick Tree of size n.

Insight 3: Frequency BIT. A Fenwick Tree where bit[k] stores the count of seen elements with rank k answers two questions in O(log n):

• update(rank, plus 1) — record that we just saw this value
• query(rank minus 1) — return how many already-seen values have a rank strictly smaller than rank

That is exactly what we need. The total work is O(n log n) for the sweep plus O(n log n) for the sort. Coordinate compression is mandatory whenever the value range is much larger than the count of values.

Visual Dry Run#

Walk through nums = [5, 2, 6, 1].

Step 0 — Coordinate compression. Sorted unique values: [1, 2, 5, 6]. Ranks: 1 to 1, 2 to 2, 5 to 3, 6 to 4. Rewritten ranks of nums: [3, 2, 4, 1].

Step 1 — Sweep right to left, maintain BIT of size 4 (initially all zeros).

BIT after each step (1-indexed):
              bit[1] bit[2] bit[3] bit[4]   meaning of result
Process 1 (rank 1):                          query(0) = 0  -> result[3] = 0
  update(1):    1      1      0      0      (BIT now stores count[1]=1)
 
Process 6 (rank 4):                          query(3) = 1  -> result[2] = 1
  update(4):    1      1      0      1
 
Process 2 (rank 2):                          query(1) = 1  -> result[1] = 1
  update(2):    1      2      0      1
 
Process 5 (rank 3):                          query(2) = 2  -> result[0] = 2
  update(3):    1      2      1      1

Final answer: [2, 1, 1, 0]. The BIT only needs a single forward walk for update and a single backward walk for query, each O(log n).

Solution (Optimal)#

Python — Fenwick Tree plus Coordinate Compression#

from typing import List
 
class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        # 1) coordinate compress values to dense ranks in [1..n]
        sorted_unique = sorted(set(nums))            # ascending unique values
        rank = {v: i + 1 for i, v in enumerate(sorted_unique)}  # 1-indexed rank map
        size = len(sorted_unique)                    # BIT length matches unique count
        bit = [0] * (size + 1)                       # 1-indexed Fenwick array
 
        def update(i: int) -> None:
            # add 1 to position i, propagate to all responsible ancestors
            while i <= size:
                bit[i] += 1
                i += i & (-i)                        # jump by lowest set bit
 
        def query(i: int) -> int:
            # prefix count of seen elements with rank in [1..i]
            s = 0
            while i > 0:
                s += bit[i]
                i -= i & (-i)                        # remove lowest set bit
            return s
 
        # 2) sweep right to left, query then update
        result = [0] * len(nums)
        for i in range(len(nums) - 1, -1, -1):
            r = rank[nums[i]]
            result[i] = query(r - 1)                 # strictly smaller seen so far
            update(r)                                # record this element
        return result

JavaScript — Fenwick Tree plus Coordinate Compression#

var countSmaller = function(nums) {
    // 1) coordinate compression
    const sortedUnique = [...new Set(nums)].sort((a, b) => a - b);
    const rank = new Map();
    sortedUnique.forEach((v, i) => rank.set(v, i + 1));   // 1-indexed
    const size = sortedUnique.length;
    const bit = new Array(size + 1).fill(0);
 
    const update = (i) => {
        // add 1 to position i, walk up using lowest set bit
        while (i <= size) {
            bit[i] += 1;
            i += i & -i;
        }
    };
 
    const query = (i) => {
        // accumulate prefix count [1..i]
        let s = 0;
        while (i > 0) {
            s += bit[i];
            i -= i & -i;
        }
        return s;
    };
 
    // 2) sweep right to left
    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);                         // count of strictly smaller seen
        update(r);                                        // mark this rank as seen
    }
    return result;
};

Complexity: Time O(n log n) — one sort plus n Fenwick operations. Space O(n) for the rank map and BIT array.

Common Mistakes#

1. Mixing 0-indexed and 1-indexed BIT. A Fenwick Tree must be 1-indexed because i & (-i) evaluates to zero at index 0, which would loop forever. Always do rank = index + 1 and size the BIT array as n + 1.
2. Querying rank instead of rank - 1. You want strictly smaller elements, so you must query the prefix that excludes the current rank. Querying rank includes equal elements and silently inflates the count.
3. Updating before querying. If you update first you accidentally count the current element itself. The order is always query, then update.
4. Forgetting deduplication during compression. sorted(nums) works but wastes BIT space when there are duplicates. Use sorted(set(nums)) so the BIT is exactly the right size.
5. Using values directly without compression. When values can be up to plus or minus 10^9, allocating a BIT of that size is impossible. Coordinate compression is not optional, it is the bridge that makes the BIT feasible.
6. Sweeping left to right. The natural reading direction is wrong here. Right to left turns "future smaller" into "already-seen smaller", which is what the BIT can answer.

Interview Tips#

• State the rank trick out loud. Interviewers grade on whether you connect "values are sparse" to "compress to ranks before indexing into a Fenwick Tree". Naming it explicitly is a strong signal.
• Sketch the BIT layout. Draw a tiny array, mark which range each bit[k] is responsible for, and show how i & (-i) traverses it. This proves you actually understand the structure rather than memorizing template code.
• Mention alternatives, then commit. A merge-sort solution and a Segment Tree are both valid. Say so, then choose BIT because the code is shorter and the constant factor smaller for pure counting queries.
• Prepare the duplicates question. If duplicates exist, do you count equal elements? Re-read the prompt — "smaller" means strictly less, so you query rank - 1, not rank.
• Discuss the merge-sort variant as your fallback. Merge sort counts inversions during the merge step. Knowing both solutions shows depth.

Follow-up Questions#

1. Count larger elements after self instead. Replace query(rank - 1) with query(size) - query(rank).
2. Count of Range Sum (LeetCode 327). Same skeleton — sweep prefix sums and ask "how many already-seen prefix sums fall in [curr - upper, curr - lower]".
3. Reverse Pairs (LeetCode 493). Count pairs where nums[i] > 2 * nums[j]. Compress both nums and 2 * nums + 1.
4. Sliding window of smaller counts. Use a Fenwick Tree plus a deque, decrementing when an element leaves the window.
5. 2D version: count points in a rectangle. Sort by x, sweep, use a BIT on compressed y-coordinates.
6. Online version (queries arrive one at a time). Use an Order-Statistics Tree (a balanced BST that supports order_of_key) for O(log n) per insert plus query.

Key Takeaways#

• The BIT plus coordinate compression pattern collapses the value space to dense ranks so a Fenwick Tree of size n can answer "how many already-seen values are smaller than k" in O(log n).
• Sweep right to left so the elements already inserted into the BIT are exactly the elements to the right of the current index.
• A Fenwick Tree is 1-indexed because i & (-i) is undefined at zero. Always shift indices by 1 before touching the BIT.
• Remember the order: query first, then update, otherwise you count the current element itself.
• Whenever the value range dwarfs the array length, reach for coordinate compression — it is the universal preprocessor for Fenwick and Segment Tree problems on values.
• The same template solves Reverse Pairs, Count of Range Sum, sliding-window inversion counts, and 2D rectangle queries — recognize the family and reuse the scaffold.