Count of Smaller Numbers After Self [Hard] — Merge Sort

Problem Statement#

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

Examples:

Input:  [5, 2, 6, 1]
Output: [2, 1, 1, 0]
 
Explanation:
  5 → elements to its right smaller than 5: [2, 1]  → count 2
  2 → elements to its right smaller than 2: [1]      → count 1
  6 → elements to its right smaller than 6: [1]      → count 1
  1 → elements to its right smaller than 1: []       → count 0
 
Input:  [-1]
Output: [0]
 
Input:  [-1, -1]
Output: [0, 0]

Constraints:

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

Why This Problem Matters#

LeetCode 315 is a FAANG staple — it appears on Amazon, Google, and Meta interview loops regularly. It is hard for a specific reason: the output is not a single number. You need to produce a value per input element, and that makes caching or reusing work across elements non-trivial.

The naive approach is obvious and wrong at scale. Every candidate who has done LC Easy/Medium problems will write the O(n²) double-loop first. Interviewers expect you to recognize its limits and pivot immediately to the O(n log n) approach.

What makes this problem genuinely educational is the insight it teaches: divide-and-conquer algorithms can carry auxiliary information for free. Merge sort does work during the merge step that is directly useful for counting inversions — you are not adding a separate pass. Once you internalize this pattern, three other LC Hard problems become immediately approachable: LC 493 (Reverse Pairs), LC 327 (Count of Range Sum), and LC 218 (The Skyline Problem).

In interviews, this problem also tests whether you can track original indices through a sorting process — a subtle implementation detail that causes most candidates to produce wrong answers even when they understand the algorithm conceptually.

The Merge Sort Insight#

The key observation: an element nums[i] gains a "smaller to its right" count whenever a right-half element jumps over it during merge sort.

Here is why that works. Merge sort divides the array in half recursively. When it merges two sorted halves, it picks elements one by one. If a right-half element is smaller than the current left-half element, that right element was originally to the right of every remaining left-half element in the original array. So it contributes +1 to each of their counts.

More precisely: when we are merging and we pick right[j] instead of left[i], it means right[j] is smaller than left[i], left[i+1], ..., left[end]. All of those remaining left elements should get their count incremented — but we do not do it one by one. Instead we track a running counter of how many right elements have been absorbed so far, and add that counter to each left element's count when we finally place it.

This is the inversion-counting trick. An inversion is a pair (i, j) where i < j but nums[i] > nums[j]. Each such inversion contributes exactly +1 to counts[i]. Merge sort counts all inversions in O(n log n) — that is the entire solution.

The one implementation catch: once you sort, you lose track of which element belonged to which original index. The fix is to sort pairs of (value, original_index) instead of raw values. When you update a count, you use the saved original index to write into the output array.

Visual Dry Run#

Let us trace the full execution on [5, 2, 6, 1].

Setup: pair each value with its original index.

indexed = [(5,0), (2,1), (6,2), (1,3)]
counts  = [0, 0, 0, 0]

Step 1 — Split recursively until base cases:

Left half:  [(5,0), (2,1)]
Right half: [(6,2), (1,3)]
 
  Left-left:  [(5,0)]   ← base case
  Left-right: [(2,1)]   ← base case
  Right-left: [(6,2)]   ← base case
  Right-right:[(1,3)]   ← base case

Step 2 — Merge [(5,0)] with [(2,1)]:

i=0 (left points to (5,0)), j=0 (right points to (2,1))
 
Compare 5 vs 2:
  5 > 2 → right element (2) is smaller than left element (5)
  j advances: j=1
  right is exhausted. Place (5,0):
    counts[0] += (len(right) - j) = (1 - 1) = 0   ← j already at end, none remain
  Wait — let me redo with the correct accounting.

Using the correct approach: we count how many right elements have already been placed when we place a left element. Call that right_placed.

right_placed = 0
 
i=0, j=0: compare 5 vs 2
  2 < 5 → place (2,1) from right first
  right_placed = 1, j=1
 
i=0, j=1 (right exhausted): place (5,0)
  counts[0] += right_placed = 1
  i=1
 
i=1, j=1 (both exhausted)
 
Merged left: [(2,1), (5,0)]
counts = [1, 0, 0, 0]

So after merging the left half, 5 has picked up a count of 1 (from 2 jumping over it).

Step 3 — Merge [(6,2)] with [(1,3)]:

right_placed = 0
 
i=0, j=0: compare 6 vs 1
  1 < 6 → place (1,3) from right
  right_placed = 1, j=1
 
i=0, j=1 (right exhausted): place (6,2)
  counts[2] += right_placed = 1
  i=1
 
Merged right: [(1,3), (6,2)]
counts = [1, 0, 1, 0]

Step 4 — Final merge of [(2,1),(5,0)] with [(1,3),(6,2)]:

right_placed = 0
 
i=0 → (2,1), j=0 → (1,3): compare 2 vs 1
  1 < 2 → place (1,3) from right
  right_placed = 1, j=1
 
i=0 → (2,1), j=1 → (6,2): compare 2 vs 6
  2 < 6 → place (2,1) from left
  counts[1] += right_placed = 1
  i=1
 
i=1 → (5,0), j=1 → (6,2): compare 5 vs 6
  5 < 6 → place (5,0) from left
  counts[0] += right_placed = 1
  i=2
 
i=2 (left exhausted): place (6,2) from right
  j=2 (right exhausted)
 
Final merged: [(1,3),(2,1),(5,0),(6,2)]
counts = [2, 1, 1, 0]

This matches the expected output exactly. Notice that 5 accumulated a count of 1 from Step 2 (when 2 jumped over it) and another 1 from Step 4 (when 1 jumped over it) — total 2. That is correct: both 2 and 1 are smaller and to the right of 5 in the original array.

Common Mistakes#

Mistake 1 — Updating counts by the wrong quantity.

A very common bug is writing counts[left[i][0]] += len(right) - j when picking a left element, or forgetting to account for the elements already placed from the right. The correct logic is to track a right_placed counter (how many right elements have been placed before this left element) and add that to counts[original_index]. Some implementations use len(right) - j at the time of placing a left element when no elements remain on the right side — this is mathematically equivalent but requires careful bookkeeping. Pick one approach and stick with it; mixing them causes off-by-one errors.

Mistake 2 — Sorting raw values instead of index-value pairs.

If you sort the numbers directly and lose original indices, you cannot write results back to the correct position in counts. Every solution must carry the original index alongside each value. Use tuples like (value, original_index) or a parallel index array.

Mistake 3 — Incorrect comparison direction.

The merge step places the smaller element first. You increment right_placed every time you place a right element. You credit right_placed to a left element when you place that left element. Reversing the comparison (left[i] < right[j]) or crediting the wrong side (crediting right elements instead of left) produces an entirely wrong answer. Draw the array on paper first and check: "when does a right element jump past a left element?"

Mistake 4 — Not handling equal elements correctly.

When left[i] == right[j], you must place the right element first. If you place the left element first (the natural tie-breaking in a stable sort), you will incorrectly credit the left element for the right elements that have not yet been placed. The problem asks for strictly smaller, so equal elements should not count — placing right first when equal prevents that.

Mistake 5 — Trying this with an in-place sort.

Merge sort can be done in-place, but the index tracking becomes extremely complex. Resist the urge to save space. Use auxiliary arrays. The O(n) extra space is already accounted for in the complexity analysis, and clean code matters in interviews.

Solutions#

Brute Force — O(n²)#

Start here to demonstrate problem understanding before optimizing.

Python#

def countSmaller(nums: list[int]) -> list[int]:
    n = len(nums)
    counts = [0] * n           # result array, one entry per element
 
    for i in range(n):         # for each element at position i
        for j in range(i + 1, n):  # scan every element to the right
            if nums[j] < nums[i]:  # found a smaller element
                counts[i] += 1    # increment count for position i
 
    return counts

JavaScript#

function countSmaller(nums) {
    const n = nums.length;
    const counts = new Array(n).fill(0);  // result array
 
    for (let i = 0; i < n; i++) {         // for each element
        for (let j = i + 1; j < n; j++) { // scan elements to the right
            if (nums[j] < nums[i]) {       // if right element is smaller
                counts[i]++;               // increment count
            }
        }
    }
 
    return counts;
}

Why it fails: For n = 10^5 this is 10^10 operations — far beyond the time limit. An interviewer may let you write this first to show understanding, but will immediately ask for better.

Optimal — Merge Sort O(n log n)#

Python#

def countSmaller(nums: list[int]) -> list[int]:
    n = len(nums)
    counts = [0] * n  # counts[i] = number of smaller elements to the right of nums[i]
 
    # Pair each value with its original index as (value, original_index).
    # We store value first so comparisons are natural, and original_index second
    # so we can write back to the correct position in counts[] after sorting.
    indexed = [(v, i) for i, v in enumerate(nums)]  # [(5,0),(2,1),(6,2),(1,3)]
 
    def merge_sort(arr):
        # Base case: a single element is trivially sorted, no inversions to count
        if len(arr) <= 1:
            return arr
 
        mid = len(arr) // 2
        left  = merge_sort(arr[:mid])   # sort and count in the left half
        right = merge_sort(arr[mid:])   # sort and count in the right half
 
        # Now merge the two sorted halves while counting inversions
        merged = []
        i = 0            # pointer into left half
        j = 0            # pointer into right half
        right_placed = 0 # how many right-half elements have been placed so far
 
        while i < len(left) and j < len(right):
            if right[j][0] < left[i][0]:
                # right[j]'s value (index 0) is smaller than left[i]'s value.
                # This right element was originally to the right of every remaining
                # left element. Place it first and record that it was absorbed.
                merged.append(right[j])
                right_placed += 1   # one more right element jumped to the left
                j += 1
            else:
                # left[i] belongs here. It has been "jumped over" by exactly
                # right_placed right elements, each of which was smaller and
                # originally to its right.
                counts[left[i][1]] += right_placed  # left[i][1] is the original index
                merged.append(left[i])
                i += 1
 
        # Drain remaining left elements — each picks up all right_placed credits
        while i < len(left):
            counts[left[i][1]] += right_placed
            merged.append(left[i])
            i += 1
 
        # Drain remaining right elements — nothing left to count for them here
        while j < len(right):
            merged.append(right[j])
            j += 1
 
        return merged
 
    merge_sort(indexed)  # result is in counts[], not the return value
    return counts

JavaScript#

function countSmaller(nums) {
    const n = nums.length;
    const counts = new Array(n).fill(0); // counts[i] tracks smaller elements to the right
 
    // Pair each value with its original index: [[value, originalIndex], ...]
    // We need original indices because sorting will rearrange elements.
    let indexed = nums.map((val, idx) => [val, idx]);
 
    function mergeSort(arr) {
        // Base case: zero or one element — already sorted, no inversions
        if (arr.length <= 1) return arr;
 
        const mid = Math.floor(arr.length / 2);
        const left  = mergeSort(arr.slice(0, mid));  // sort left half
        const right = mergeSort(arr.slice(mid));      // sort right half
 
        // Merge two sorted halves, counting how many right elements jump over left elements
        const merged = [];
        let i = 0;            // pointer into left half
        let j = 0;            // pointer into right half
        let rightPlaced = 0;  // count of right-half elements placed before current left element
 
        while (i < left.length && j < right.length) {
            if (right[j][0] < left[i][0]) {
                // right[j] is smaller — it jumps over all remaining left elements.
                // Place it and record it.
                merged.push(right[j]);
                rightPlaced++;  // one more right element absorbed to the left
                j++;
            } else {
                // left[i] belongs here. It was jumped over by rightPlaced right elements.
                // Each of those was smaller and originally to the right of left[i].
                counts[left[i][1]] += rightPlaced;  // left[i][1] is the original index
                merged.push(left[i]);
                i++;
            }
        }
 
        // Drain remaining left elements — they all absorb the full rightPlaced count
        while (i < left.length) {
            counts[left[i][1]] += rightPlaced;
            merged.push(left[i]);
            i++;
        }
 
        // Drain remaining right elements — no left elements remain to update
        while (j < right.length) {
            merged.push(right[j]);
            j++;
        }
 
        return merged;
    }
 
    mergeSort(indexed);  // side effect: fills the counts array
    return counts;
}

Complexity Analysis#

The merge sort solution has a recursive call stack of depth O(log n), and each level does O(n) work total, giving O(n log n). The indexed array and merge buffers each use O(n) space.

Follow-up Questions#

Interviewers at top companies frequently follow up with one or more of these after you solve LC 315.

1. Can you solve it with a Binary Indexed Tree (Fenwick Tree)?#

Yes. The BIT approach works as follows:

1. Coordinate compress nums to the range [1, k] where k is the number of distinct values. This maps arbitrary values to small integers suitable for BIT indices.
2. Process right to left. For each element, query the BIT for the prefix sum at compressed_value - 1. That prefix sum equals the count of already-inserted elements that are smaller — which are elements to the right of the current position.
3. Update the BIT at compressed_value by +1, recording that this element exists.

The BIT approach has the same asymptotic complexity as merge sort (O(n log n)) but avoids recursion overhead. It is often faster in practice because the BIT operations are simple array accesses with bit manipulation. The tradeoff is the coordinate compression step adds code complexity.

2. LC 493 — Reverse Pairs#

LC 493 asks: count pairs (i, j) with i < j and nums[i] > 2 * nums[j]. This is the same inversion-counting pattern but with a different comparison predicate. The merge sort approach applies directly — you count qualifying pairs during the merge step (using a two-pointer scan before the actual merge), then merge normally. Because the condition is nums[i] > 2 * nums[j] rather than nums[i] > nums[j], you cannot combine counting and merging into one pass; you need two separate passes per merge step.

3. LC 327 — Count of Range Sum#

LC 327 asks: given an array nums, count the number of range sums sum(i, j) that lie in [lower, upper]. Convert to prefix sums, then count pairs of prefix sums where the difference falls in the target range. This again uses merge sort with modified counting — during the merge step, a two-pointer approach finds qualifying prefix sum pairs in O(n) per level.

All three problems share the same structure: divide into halves, count cross-half relationships during merge, recurse. Recognizing this pattern in an interview signals deep algorithmic fluency.

This Pattern Solves#

The merge-sort inversion-counting pattern applies whenever you need to count ordered pairs (i, j) with i < j satisfying some comparison condition on nums[i] and nums[j]:

• Count inversions in an array (the classic textbook problem)
• LC 315 — Count of Smaller Numbers After Self
• LC 493 — Reverse Pairs (nums[i] > 2 * nums[j])
• LC 327 — Count of Range Sum (prefix sum differences in a range)
• Number of swaps needed to sort an array (equals total inversions)
• Detecting nearly-sorted arrays efficiently

Any time the brute force is "for every pair, check a condition" and n is large, ask yourself: can divide-and-conquer count cross-half pairs in O(n) during the merge step? If yes, you have an O(n log n) solution.

Key Takeaways#

• This problem is equivalent to counting inversions: for each index i, count pairs (i, j) with j > i and nums[j] < nums[i].
• Merge sort counts these inversions for free: each time a right-half element is placed before a left-half element during merge, it contributes +1 to every remaining left element's count.
• Always sort index-value pairs (value, original_index) — without original indices, you cannot write results back to the correct position in the output array.
• Track right_placed (count of right-half elements already merged) and credit it to each left element when that left element is placed.
• When equal elements appear (left[i] == right[j]), place the right element first to avoid false inversions — the problem asks for strictly smaller.
• O(n log n) time, O(n) space; the same pattern applies to LC 493 (Reverse Pairs) and LC 327 (Count of Range Sum).
• A Fenwick Tree (BIT) with coordinate compression is an alternative O(n log n) approach that avoids recursion overhead and is often faster in practice.