LeetCode 315: Count of Smaller Numbers After Self

i recently solved the count of smaller numbers after self problem on leetcode, and it’s a great example of advanced algorithms and data structures. this hard problem tests your understanding of merge sort, counting inversions, and efficient problem-solving techniques.

Problem Statement

you are given an integer array nums and you have to return a new counts array. the counts array has the property 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]

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]

example 3:

input: nums = [-1,-1]
output: [0,0]

My Approach

when i first saw this problem, i immediately thought about the naive O(n²) approach, but i knew there had to be a more efficient solution. the key insight is using merge sort with counting to achieve O(n log n) time complexity.

Initial Thoughts

i started by thinking about different approaches:

naive approach - O(n²) time complexity, too slow
binary indexed tree - efficient but complex implementation
merge sort with counting - O(n log n) and easier to understand
segment tree - another efficient approach but more complex

Solution Strategy

i decided to use a merge sort with counting approach with the following strategy:

index tracking - keep track of original indices during sorting
merge sort - sort the array while counting inversions
counting logic - count smaller elements during merge phase
result building - build result array based on original positions
typescript implementation - use type safety and modern features

My Solution

function countsmaller(nums: number[]): number[] {
    const n = nums.length;
    const result: number[] = new array(n).fill(0);
    
    // create array of [value, originalindex] pairs
    const indexednums: [number, number][] = nums.map((num, index) => [num, index]);
    
    function mergesort(arr: [number, number][], start: number, end: number): void {
        if (start >= end) return;
        
        const mid = math.floor((start + end) / 2);
        mergesort(arr, start, mid);
        mergesort(arr, mid + 1, end);
        merge(arr, start, mid, end);
    }
    
    function merge(arr: [number, number][], start: number, mid: number, end: number): void {
        const left = arr.slice(start, mid + 1);
        const right = arr.slice(mid + 1, end + 1);
        
        let i = 0, j = 0, k = start;
        let smallercount = 0;
        
        while (i < left.length && j < right.length) {
            if (left[i][0] <= right[j][0]) {
                // update count for left element
                result[left[i][1]] += smallercount;
                arr[k++] = left[i++];
            } else {
                // count smaller elements from left
                smallercount++;
                arr[k++] = right[j++];
            }
        }
        
        // handle remaining left elements
        while (i < left.length) {
            result[left[i][1]] += smallercount;
            arr[k++] = left[i++];
        }
        
        // handle remaining right elements
        while (j < right.length) {
            arr[k++] = right[j++];
        }
    }
    
    mergesort(indexednums, 0, n - 1);
    return result;
}

Code Breakdown

let me walk through how this solution works:

1. Initialization

const n = nums.length;
const result: number[] = new array(n).fill(0);
const indexednums: [number, number][] = nums.map((num, index) => [num, index]);

we set up our data structures:

result array: initialize with zeros for all positions
indexed array: create pairs of [value, originalindex]
length tracking: store array length for efficiency

2. Index Tracking Setup

const indexednums: [number, number][] = nums.map((num, index) => [num, index]);

we create indexed pairs:

value: the actual number from input
originalindex: the position in original array
purpose: preserve original positions during sorting

3. Merge Sort Function

function mergesort(arr: [number, number][], start: number, end: number): void {
    if (start >= end) return;
    
    const mid = math.floor((start + end) / 2);
    mergesort(arr, start, mid);
    mergesort(arr, mid + 1, end);
    merge(arr, start, mid, end);
}

the merge sort function:

base case: single element or empty range
divide: split array into two halves
conquer: recursively sort each half
combine: merge sorted halves with counting

4. Merge Function with Counting

function merge(arr: [number, number][], start: number, mid: number, end: number): void {
    const left = arr.slice(start, mid + 1);
    const right = arr.slice(mid + 1, end + 1);
    
    let i = 0, j = 0, k = start;
    let smallercount = 0;
    
    while (i < left.length && j < right.length) {
        if (left[i][0] <= right[j][0]) {
            // update count for left element
            result[left[i][1]] += smallercount;
            arr[k++] = left[i++];
        } else {
            // count smaller elements from left
            smallercount++;
            arr[k++] = right[j++];
        }
    }
    
    // handle remaining elements
    while (i < left.length) {
        result[left[i][1]] += smallercount;
        arr[k++] = left[i++];
    }
    
    while (j < right.length) {
        arr[k++] = right[j++];
    }
}

the merge function with counting:

split arrays: create left and right subarrays
counting logic: track smaller elements from right half
update results: add counts to original positions
merge process: combine sorted arrays

5. Counting Logic

if (left[i][0] <= right[j][0]) {
    // update count for left element
    result[left[i][1]] += smallercount;
    arr[k++] = left[i++];
} else {
    // count smaller elements from left
    smallercount++;
    arr[k++] = right[j++];
}

the key counting logic:

left element smaller: add current count to result
right element smaller: increment count for future left elements
original index: use stored index to update correct position

Example Walkthrough

let’s trace through the example: nums = [5,2,6,1]

step 1: create indexed array
[(5,0), (2,1), (6,2), (1,3)]

step 2: merge sort with counting
- divide: [(5,0), (2,1)] and [(6,2), (1,3)]
- sort left: [(2,1), (5,0)] (count: 1 for index 0)
- sort right: [(1,3), (6,2)] (count: 1 for index 2)
- merge: [(1,3), (2,1), (5,0), (6,2)]
  - (1,3): count = 0
  - (2,1): count = 1 (from right half)
  - (5,0): count = 2 (from right half)
  - (6,2): count = 0

result: [2,1,1,0]

Time and Space Complexity

time complexity: O(n log n) where n is the number of elements
space complexity: O(n) for additional indexed array

the algorithm is efficient because:

merge sort provides O(n log n) time complexity
we only need O(n) additional space
counting is done during the merge phase

Key Insights

merge sort approach - use sorting to achieve efficient counting
index tracking - preserve original positions during sorting
counting during merge - count smaller elements during merge phase
typescript benefits - type safety and better debugging

Alternative Approaches

i also considered:

binary indexed tree (fenwick tree) - O(n log n) time
- more complex implementation
- efficient for range queries
- harder to understand and debug
segment tree - O(n log n) time
- another efficient approach
- more complex than merge sort
- good for range operations
naive approach - O(n²) time
- simple implementation
- too slow for large inputs
- not suitable for leetcode
avl tree - O(n log n) time
- self-balancing binary search tree
- complex implementation
- efficient insertion and counting

Edge Cases to Consider

empty array - return empty array
single element - return [0]
duplicate elements - handle equal elements correctly
negative numbers - handle negative values
large arrays - ensure efficient performance
all same values - handle repeated values

TypeScript-Specific Features

type annotations - explicit typing for better code clarity
tuple types - [number, number] for indexed pairs
array methods - map, slice, fill for efficient operations
function signatures - clear parameter and return types
strict typing - catch errors at compile time

Lessons Learned

this problem taught me:

merge sort applications - beyond just sorting
counting inversions - using sorting for counting
index preservation - maintaining original positions
algorithmic thinking - choosing the right approach

Real-World Applications

this problem has applications in:

data analysis - finding relative rankings
statistics - calculating percentiles and ranks
machine learning - feature ranking and selection
financial analysis - relative performance metrics

Conclusion

the count of smaller numbers after self problem is an excellent exercise in advanced algorithms and data structures. the key insight is using merge sort with counting to achieve efficient O(n log n) time complexity while maintaining code clarity.

you can find my complete solution on leetcode.

this is part of my leetcode problem-solving series. i’m documenting my solutions to help others learn and to track my own progress.