Count Smaller After Self LeetCode 315

LeetCode 315 Count of Smaller Numbers After Self presents an integer array nums and asks you to return a counts array where counts[i] equals the number of elements to the right of nums[i] that are strictly smaller than nums[i]. Each position in the output independently counts how many values in the suffix are smaller — this is not a global sort but a per-element query over a varying suffix window.

For example, given nums = [5, 2, 6, 1], the answer is [2, 1, 1, 0]. At index 0 the value 5 has two smaller elements to its right: 2 and 1. At index 1 the value 2 has one smaller element to its right: 1. At index 2 the value 6 has one smaller element: 1. At index 3 the value 1 is the last element so its count is 0. A single-element array always returns [0].

The input constraints are what make this problem interesting: nums can have up to 10^5 elements with values ranging from -10^4 to 10^4. The naive O(n^2) solution that scans all right neighbors for each element exceeds time limits. An efficient solution must exploit structure in the problem — specifically, the insight that inversion counting during merge sort and Binary Indexed Tree prefix queries both solve this in O(n log n).

The brute force approach iterates over each index i, then scans all indices j > i to count elements where nums[j] < nums[i]. This nested loop is straightforward to implement and easy to verify for correctness, but its O(n^2) time complexity makes it untenable for the full input range. At n = 10^5, the nested loop performs roughly 5 * 10^9 comparisons — well beyond the ~10^8 operations per second budget that competitive programming judges allow.

Each element independently needs information about its entire suffix, and suffixes overlap heavily: the suffix for index 0 contains all n-1 remaining elements, the suffix for index 1 contains n-2 elements, and so on. The total work is proportional to n + (n-1) + ... + 1 = n*(n+1)/2. No caching of intermediate results is straightforward because each element uses a different suffix window. A fundamentally different algorithmic approach is required.

Space complexity of the brute force is O(1) extra (beyond the output array), which is technically optimal, but the quadratic time makes it unusable. Both the merge sort and BIT approaches trade a modest O(n) or O(n log n) space overhead for the O(n log n) time improvement that makes the solution viable for the full constraint range.

The merge sort approach modifies the standard merge sort algorithm to count inversions as a byproduct of the sort. The central idea is: when an element from the right half is placed before elements from the left half during a merge, each such placement represents an inversion — the right element is smaller than the remaining left elements, meaning those left elements each have one more "smaller element to the right" count.

The critical implementation detail is index tracking. The output array counts must map back to the original positions, but merge sort rearranges elements. To handle this, instead of sorting the raw values array, sort an array of (value, original_index) pairs. When a merge places a right-half element before left-half elements, the counts at the original indices of those left-half elements are incremented by the number of right-half elements that have already been placed (those that came before in the current merge step).

The recursion divides the array in half, recursively sorts and counts for each half, then merges. The merge step is where all the counting happens. Because the two halves are already internally sorted after the recursive calls, the merge can use a two-pointer technique to identify inversions in O(n) per level, giving O(n log n) total. The counts array is initialized to all zeros and accumulated across all merge steps in the recursion tree.

During the merge of a sorted left half and a sorted right half, the two-pointer process compares left[i] and right[j]. If right[j] < left[i], then because the left half is sorted, right[j] is also smaller than left[i+1], left[i+2], all the way through left[end]. Rather than counting each of those inversions individually, the algorithm can count them all at once: right[j] contributes one to the count for every remaining left element, which is (left.length - i) elements at the moment right[j] is placed.

Equivalently, the algorithm can track right_count: the number of right-half elements that have been placed into the merged output so far. Each time a left-half element left[i] is placed into the output, right_count elements from the right half have already been placed that are smaller than left[i] (because they were placed first and the right half is sorted). Therefore counts[original_index_of_left[i]] += right_count at the moment left[i] is placed.

This counting is exact because: (1) both halves are sorted, so the order of placement is deterministic; (2) right elements placed before a left element are exactly those that are smaller than the left element within this merge; (3) inversions between elements in the same half are already counted in the recursive calls. Together these three properties guarantee that every inversion pair (i, j) with i < j and nums[i] > nums[j] is counted exactly once across all merge levels.

A Binary Indexed Tree (BIT), also called a Fenwick Tree, provides an alternative O(n log n) approach. The key operation needed is: given the elements already processed, how many are strictly smaller than the current element? A BIT supports prefix sum queries and point updates in O(log n) each, making it ideal. The algorithm processes elements right-to-left: for each element, query the BIT for count of elements smaller than it (already inserted from its right), then insert it.

Because BIT indices must be positive integers in a bounded range, coordinate compression is required first. Sort the unique values of nums, assign each unique value a rank from 1 to m (where m is the number of distinct values). Replace each element in nums with its rank. Now queries for "how many inserted elements have rank < current_rank" are prefix sum queries: query(current_rank - 1). After querying, update the BIT at current_rank to record that this value has been seen.

The BIT approach is iterative (no recursion) and avoids the complexity of tracking index pairs through a sort. However, the coordinate compression step requires extra code and the constant factors are comparable to merge sort. Both approaches have O(n log n) time and O(n) space. In practice, the BIT approach can be slightly faster due to better cache behavior and simpler control flow, while merge sort is more natural for candidates familiar with divide-and-conquer.

In Python, the merge sort solution creates indexed pairs with enumerate, initializes a counts list of zeros, and defines a nested merge_sort function. The function splits the list in half, recursively processes each half, then merges using a right_count variable. For each left element placed, counts[orig_idx] += right_count. For each right element placed, right_count += 1. The time complexity is O(n log n) for the sort with O(n) per merge level across O(log n) levels. Space is O(n) for the temporary merged arrays at each level.

In Java, the approach uses an int[][] array where each entry is {value, originalIndex}. A helper method mergeSort takes the array, counts array, left bound, and right bound. It splits at mid, recurses on both halves, then calls a merge helper. The merge helper uses a rightCount int variable and two ArrayDeques or a temporary array. When a left element is chosen, counts[left[i][1]] += rightCount. When a right element is chosen, rightCount++. The final merged array overwrites the subarray in-place using System.arraycopy.

A common pitfall is forgetting to pass and mutate the original counts array through the recursion — if counts is declared locally inside merge_sort it will be reset on each call. Both implementations must also handle the edge case where the input has length 1, returning immediately without counting. For the BIT version in Python, a simple list-based BIT with 1-indexed operations suffices; in Java, an int[] of size n+2 with the standard Fenwick Tree update and query loops works correctly.

Reverse Pairs (LeetCode 493) is a direct extension of this problem: count pairs (i, j) where i < j and nums[i] > 2 * nums[j]. The same modified merge sort framework applies, but the counting condition changes from strict less-than to a 2x threshold. The key difference is that the counting and placement steps must be separated — you first count across halves using two pointers, then perform the actual merge separately, because the 2x condition breaks the one-pass counting property.

Count Inversions (classical algorithm problem) is the direct predecessor: count total pairs (i, j) where i < j and nums[i] > nums[j]. This is essentially the sum of all counts[i] from LeetCode 315. The merge sort approach for the classical inversion count is simpler because you only need a global counter rather than per-element counts. Range Sum Query 2D — Mutable (LeetCode 308) applies 2D BIT techniques, demonstrating how prefix sum structures generalize beyond 1D.

The merge sort inversion counting family — LeetCode 315, 493, and classical inversion count — represents a powerful pattern where the sort itself computes a useful property. Divide and conquer problems like this appear at the hard level and reward candidates who understand not just the algorithm but why the recursion structure guarantees each pair is counted exactly once. Mastering this family of problems demonstrates strong algorithmic fundamentals for senior engineering interviews.