315 - Count of Smaller Numbers After Self

Difficulty: Hard | Pattern: Binary Indexed Tree / Merge Sort | Company tags: Amazon, Google, Facebook

Problem Statement

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].

Example 1:

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

Example 2:

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

Approach: Binary Indexed Tree (Fenwick Tree) — O(n log n)

Key insight: Process from right to left. For each element, query how many already-seen elements are smaller (lower rank). Coordinate compress to handle arbitrary values.

def countSmaller(nums: list[int]) -> list[int]:
    sorted_unique = sorted(set(nums))
    rank = {v: i+1 for i, v in enumerate(sorted_unique)}
    n = len(nums)
    m = len(sorted_unique)
    
    bit = [0] * (m + 1)
    
    def update(i):
        while i <= m:
            bit[i] += 1
            i += i & (-i)
    
    def query(i):
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & (-i)
        return s
    
    result = []
    for x in reversed(nums):
        r = rank[x]
        result.append(query(r - 1))  # count of elements with rank < r
        update(r)
    
    return result[::-1]

Algorithm Flow

Dry Run

nums = [5,2,6,1]

Ranks: 1→1, 2→2, 5→3, 6→4

Process right to left:

x	rank	query(rank-1)	update(rank)	result
1	1	query(0)=0	update(1)	[0]
6	4	query(3)=1 (1 is there)	update(4)	[0,1]
2	2	query(1)=1 (1 is there)	update(2)	[0,1,1]
5	3	query(2)=2 (1,2 are there)	update(3)	[0,1,1,2]

Reversed: [2,1,1,0] ✓

Complexity

• Time: O(n log n)
• Space: O(n)

Key Terms

Term	Definition
Binary Indexed Tree (Fenwick Tree)	A data structure supporting O(log n) prefix-sum updates and queries.
Coordinate compression	Mapping arbitrary values to a dense rank range so they can index an array/tree.
Prefix count query	Asking "how many elements with rank ≤ r have been seen so far?"
Right-to-left processing	Traversal order that lets each element's "count of smaller to the right" be answered incrementally.
Inversion counting	The general technique of counting out-of-order pairs, of which this problem is an instance.

FAQ

1. Why process the array right to left instead of left to right? Because we need to count elements to the right that are smaller. Processing right to left lets us query the BIT for "already inserted, smaller rank" before inserting the current element.
2. Can this be solved with merge sort instead of a BIT? Yes — a modified merge sort counts cross-inversions during the merge step and achieves the same O(n log n) time without coordinate compression's rank map, though it needs to track original indices.
3. What if nums contains duplicate values? Coordinate compression uses sorted(set(nums)), so duplicates share the same rank; querying rank-1 still correctly excludes equal values (only strictly smaller ones count).
4. What's the time complexity if we used a naive O(n²) approach? O(n²) — for each element, scan all elements to its right. This is a valid brute-force but fails for large n (e.g., n = 10^5).
5. How would the solution change if we needed counts of smaller-or-equal elements? Query rank instead of rank - 1 in the BIT, since we now want to include equal-ranked elements already inserted.

Quick Revision

• Problem: for each index, count smaller elements strictly to its right.
• Brute force is O(n²); optimal is O(n log n) using a BIT or merge sort.
• Coordinate-compress values to ranks 1..m to bound the BIT size.
• Process the array from right to left.
• Before inserting the current value, query count(rank - 1) — smaller values already seen.
• Insert (update) the current value's rank into the BIT.
• Reverse the collected results at the end since they were built back-to-front.
• BIT operations (update, query) are O(log m) each, giving O(n log n) overall.

Related Problems

• 327 - Count of Range Sum — same BIT/merge-sort inversion-counting pattern.
• 493 - Reverse Pairs — counts pairs i < j with nums[i] > 2*nums[j], solved with the same technique.
• Merge-sort-based inversion counting is the classic alternative pattern for this problem.