LeetCode 315 - Count of Smaller Numbers After Self

LeetCode Problem 315

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set

Solution

Problem Understanding

The problem asks us to compute, for every element in the array, how many elements to its right are strictly smaller than it.

Given an array nums, we must return another array counts of the same length. For each index i, counts[i] represents the number of indices j such that:

• j > i
• nums[j] < nums[i]

In other words, for every number, we look only at the elements that appear after it in the array and count how many of them are smaller.

For example, in the array [5,2,6,1]:

• 5 has two smaller numbers after it, 2 and 1
• 2 has one smaller number after it, 1
• 6 has one smaller number after it, 1
• 1 has none

So the result is [2,1,1,0].

The constraints are important:

• The array can contain up to 10^5 elements
• Values range from -10^4 to 10^4

A naive solution that compares every pair of elements would require O(n^2) time, which becomes too slow when n = 100000. A quadratic algorithm would potentially perform around 10^10 comparisons, which is not feasible within typical LeetCode time limits.

The problem guarantees that the input array is non-empty, but several edge cases still matter:

• Arrays with one element
• Arrays with duplicate values
• Arrays already sorted ascending
• Arrays sorted descending
• Negative numbers
• Repeated negative numbers

Handling duplicates correctly is especially important because we only count strictly smaller elements, not equal ones.

Approaches

Brute Force Approach

The simplest approach is to process every index independently.

For each element nums[i], we scan all elements to its right and count how many are smaller than nums[i]. This directly follows the problem definition and is easy to implement.

The algorithm works because it explicitly checks every valid pair (i, j) where j > i. If nums[j] < nums[i], we increment the count for index i.

However, this approach performs poorly for large arrays. Since each element may scan nearly the entire remainder of the array, the total number of comparisons becomes:

$$1 + 2 + 3 + \dots + (n-1) = O(n^2)$$

With n = 100000, this is too slow.

Optimal Approach, Modified Merge Sort

The key insight is that this problem resembles inversion counting.

During merge sort, the array is repeatedly divided and merged in sorted order. While merging two sorted halves, we can determine how many elements from the right half are smaller than elements from the left half.

Suppose we are merging:

• Left half: sorted elements originally appearing earlier
• Right half: sorted elements originally appearing later

If an element from the right half is placed before an element from the left half during merging, then that right-side element is smaller and originally appeared after the left-side element in the array.

This means we can accumulate counts during the merge process itself.

The important optimization is that merge sort already organizes elements in sorted order, allowing us to count many relationships at once instead of checking every pair individually.

Because merge sort runs in O(n log n) time, this approach is efficient enough for the constraints.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1) extra	Compare every element with all elements to its right
Optimal Merge Sort	O(n log n)	O(n)	Counts smaller elements during merge operations

Algorithm Walkthrough

Optimal Merge Sort Algorithm

1. Create an array of pairs containing both the value and its original index.

We cannot sort the array directly because we must return answers in the original order. Each element is stored as:

(value, original_index)

Example:

nums = [5,2,6,1]

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

2. Initialize a result array filled with zeros.

This array stores the final counts for each original index.

result = [0,0,0,0]

3. Recursively divide the array using merge sort.

Merge sort splits the array into halves until each subarray contains one element.

Single-element arrays are already sorted. 4. Merge the two sorted halves while counting smaller elements.

During merging, maintain two pointers:

• One pointer for the left half
• One pointer for the right half

Also maintain a variable:

right_smaller_count

This represents how many elements from the right half have already been placed before the current left element. 5. Compare elements from both halves.

If the right element is smaller:

right_value < left_value

then:

• The right element should be merged first
• It contributes one smaller element for all remaining left elements
• Increment right_smaller_count

6. When placing a left element into the merged array, update its answer.

Since right_smaller_count elements from the right half have already moved ahead of it, all those elements are:

• Originally to its right
• Smaller than it

So:

result[left_index] += right_smaller_count

7. Continue until the merge completes.

Eventually, every merge operation contributes counts to the appropriate indices. 8. Return the result array after merge sort finishes.

Why it works

The correctness comes from the merge sort invariant.

At every merge step:

• The left half contains elements that originally appeared earlier
• The right half contains elements that originally appeared later
• Both halves are already sorted

Whenever an element from the right half moves ahead of a left-half element during merging, it represents a smaller element appearing later in the original array.

Because merge sort processes all such relationships exactly once, every smaller-right relationship is counted correctly.

Python Solution

from typing import List

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [0] * n
        
        indexed_nums = [(nums[i], i) for i in range(n)]
        
        def merge_sort(left: int, right: int) -> None:
            if left >= right:
                return
            
            mid = (left + right) // 2
            
            merge_sort(left, mid)
            merge_sort(mid + 1, right)
            
            merge(left, mid, right)
        
        def merge(left: int, mid: int, right: int) -> None:
            temp = []
            
            i = left
            j = mid + 1
            
            right_smaller_count = 0
            
            while i <= mid and j <= right:
                if indexed_nums[j][0] < indexed_nums[i][0]:
                    temp.append(indexed_nums[j])
                    right_smaller_count += 1
                    j += 1
                else:
                    value, original_index = indexed_nums[i]
                    result[original_index] += right_smaller_count
                    temp.append(indexed_nums[i])
                    i += 1
            
            while i <= mid:
                value, original_index = indexed_nums[i]
                result[original_index] += right_smaller_count
                temp.append(indexed_nums[i])
                i += 1
            
            while j <= right:
                temp.append(indexed_nums[j])
                j += 1
            
            for k in range(len(temp)):
                indexed_nums[left + k] = temp[k]
        
        merge_sort(0, n - 1)
        
        return result

The implementation begins by pairing each value with its original index. This is necessary because merge sort rearranges elements, but the final answers must correspond to the original positions.

The result array stores the number of smaller elements for each index.

The recursive merge_sort function divides the array until subarrays contain only one element. Since single-element arrays are already sorted, the recursion then starts merging upward.

The real logic happens inside the merge function. Two sorted halves are merged while tracking how many right-half elements have already been placed before the current left-half element.

Whenever a right-side value is smaller, it increments right_smaller_count. Later, when a left-side element is inserted into the merged array, that count is added to its answer.

Finally, the merged result is copied back into indexed_nums, preserving sorted order for higher merge levels.

Go Solution

func countSmaller(nums []int) []int {
	n := len(nums)

	result := make([]int, n)

	type Pair struct {
		value int
		index int
	}

	indexedNums := make([]Pair, n)

	for i := 0; i < n; i++ {
		indexedNums[i] = Pair{
			value: nums[i],
			index: i,
		}
	}

	var mergeSort func(int, int)

	mergeSort = func(left int, right int) {
		if left >= right {
			return
		}

		mid := (left + right) / 2

		mergeSort(left, mid)
		mergeSort(mid+1, right)

		merge(left, mid, right)
	}

	merge := func(left int, mid int, right int) {
		temp := make([]Pair, 0, right-left+1)

		i := left
		j := mid + 1

		rightSmallerCount := 0

		for i <= mid && j <= right {
			if indexedNums[j].value < indexedNums[i].value {
				temp = append(temp, indexedNums[j])
				rightSmallerCount++
				j++
			} else {
				result[indexedNums[i].index] += rightSmallerCount
				temp = append(temp, indexedNums[i])
				i++
			}
		}

		for i <= mid {
			result[indexedNums[i].index] += rightSmallerCount
			temp = append(temp, indexedNums[i])
			i++
		}

		for j <= right {
			temp = append(temp, indexedNums[j])
			j++
		}

		for k := 0; k < len(temp); k++ {
			indexedNums[left+k] = temp[k]
		}
	}

	mergeSort(0, n-1)

	return result
}

The Go implementation follows the same algorithmic structure as the Python solution. The main difference is that Go requires an explicit Pair struct to store both the value and original index.

Slices are used for temporary merge storage. Since Go does not support nested function declarations in exactly the same way as Python, function variables are declared before assignment.

Integer overflow is not a concern because the constraints are small enough for Go's standard int type.

Worked Examples

Example 1

Input:

[5,2,6,1]

Initial indexed array:

Position	Pair
0	(5,0)
1	(2,1)
2	(6,2)
3	(1,3)

Initial result:

[0,0,0,0]

Merge Step: [5] and [2]

Compare:

2 < 5

So:

• Move (2,1) first
• right_smaller_count = 1

Then place (5,0):

result[0] += 1

Result becomes:

[1,0,0,0]

Merged section:

[(2,1), (5,0)]

Merge Step: [6] and [1]

Compare:

1 < 6

Move (1,3) first.

Then place (6,2):

result[2] += 1

Result becomes:

[1,0,1,0]

Merged section:

[(1,3), (6,2)]

Final Merge

Merge:

[(2,1), (5,0)]
[(1,3), (6,2)]

Compare 1 and 2:

1 < 2

Move (1,3) first.

right_smaller_count = 1

Now compare 6 and 2.

2 is smaller, so:

result[1] += 1

Result:

[1,1,1,0]

Now compare 6 and 5.

5 is smaller, so:

result[0] += 1

Final result:

[2,1,1,0]

Example 2

Input:

[-1]

Single-element arrays already satisfy merge sort base conditions.

Output:

[0]

Example 3

Input:

[-1,-1]

During merging:

-1 < -1

is false because we only count strictly smaller elements.

No counts are added.

Output:

[0,0]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Merge sort performs log n levels of recursion and processes all elements at each level
Space	O(n)	Extra arrays are needed during merge operations

The time complexity comes from standard merge sort behavior. The array is repeatedly divided into halves, producing log n recursive levels. At each level, all n elements participate in merging exactly once.

The space complexity is O(n) because temporary arrays are created during merging, and the indexed representation also stores all elements.

Test Cases

sol = Solution()

assert sol.countSmaller([5,2,6,1]) == [2,1,1,0]  # standard example
assert sol.countSmaller([-1]) == [0]  # single element
assert sol.countSmaller([-1,-1]) == [0,0]  # duplicates

assert sol.countSmaller([1,2,3,4]) == [0,0,0,0]  # ascending order
assert sol.countSmaller([4,3,2,1]) == [3,2,1,0]  # descending order

assert sol.countSmaller([2,0,1]) == [2,0,0]  # mixed ordering
assert sol.countSmaller([1,1,1,1]) == [0,0,0,0]  # all equal

assert sol.countSmaller([-5,-2,-6,-1]) == [1,1,0,0]  # negative numbers

assert sol.countSmaller([10]) == [0]  # minimum size input

assert sol.countSmaller([3,2,2,6,1]) == [3,1,1,1,0]  # duplicates with smaller elements

assert sol.countSmaller([10000,-10000,0]) == [2,0,0]  # extreme constraint values

Test Summary

Test	Why
[5,2,6,1]	Standard reference example
[-1]	Smallest possible input
[-1,-1]	Ensures duplicates are not counted
[1,2,3,4]	No smaller elements to the right
[4,3,2,1]	Maximum smaller counts
[2,0,1]	Mixed ordering case
[1,1,1,1]	All elements identical
[-5,-2,-6,-1]	Negative values
[10]	Boundary size validation
[3,2,2,6,1]	Duplicate handling during merge
[10000,-10000,0]	Extreme value constraints

Edge Cases

Arrays With Duplicate Values

Duplicate handling is one of the easiest places to introduce bugs. The problem asks for strictly smaller elements, not smaller-or-equal elements.

For example:

[-1,-1]

should produce:

[0,0]

During merging, the algorithm only increments counts when:

right_value < left_value

not when values are equal. This guarantees duplicates are handled correctly.

Already Sorted Ascending Arrays

In an ascending array such as:

[1,2,3,4]

every element already has no smaller elements to its right.

A faulty implementation might accidentally count inversions incorrectly during merging. In this implementation, the right-side element is only moved first if it is strictly smaller, so no counts are added.

The result correctly remains:

[0,0,0,0]

Descending Arrays

Descending arrays create the maximum possible counts.

Example:

[4,3,2,1]

Every element is larger than all elements after it.

This case stresses whether the merge process correctly accumulates many smaller elements across recursive merge levels. The algorithm handles this naturally because each right-half insertion increments right_smaller_count, which is then added to all remaining left-half elements.

The final result becomes:

[3,2,1,0]

which is correct.