Count of Smaller Numbers After Self - Practice Coding Problems

Count of Smaller Numbers After Self - Problem

Array Binary Search Divide and Conquer Binary Indexed Tree Segment Tree Merge Sort Ordered Set Hard

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

For each element at index i, count how many elements with indices j > i satisfy nums[j] < nums[i].

Example:

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

Input & Output

Example 1 — Basic Case

$ Input: nums = [5,2,6,1]

› Output: [2,1,1,0]

💡 Note: 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 — Single Element

$ Input: nums = [1]

› Output: [0]

💡 Note: There are no elements to the right of the single element, so count is 0.

Example 3 — Sorted Array

$ Input: nums = [1,2,3,4]

› Output: [0,0,0,0]

💡 Note: Array is sorted in ascending order, so no element has smaller elements to its right.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁴ ≤ nums[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array [5,2,6,1] with indices

Count Process

For each element, count smaller elements to the right

Result Array

Output [2,1,1,0] with counts

Key Takeaway

🎯 Key Insight: We need to efficiently count inversions - use merge sort or advanced data structures to achieve O(n log n) time complexity

Asked in

G Google 15 a Amazon 12 f Facebook 8 M Microsoft 6

The key insight is to use advanced data structures or divide-and-conquer to avoid O(n²) brute force. Best approach is merge sort with inversion counting achieving optimal Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n²)	O(1)	For each element, scan all elements to its right and count smaller ones
Merge Sort with Counting	O(n log n)	O(n)	Use modified merge sort to count inversions while merging sorted subarrays
Binary Search with Sorted Array	O(n²)	O(n)	Process array from right to left, maintain sorted list and use binary search to count smaller elements

Brute Force — Algorithm Steps

Iterate through each element in the array
For each element, scan all elements to its right
Count elements smaller than current element
Store count in result array

Visualization

Tap to expand

Step-by-Step Walkthrough

Start with first element

Check all elements to the right

Count smaller elements

Increment counter for each smaller element found

Repeat for all elements

Process each position in the array

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;
    int* counts = (int*)calloc(numsSize, sizeof(int));
    
    for (int i = 0; i < numsSize; i++) {
        for (int j = i + 1; j < numsSize; j++) {
            if (nums[j] < nums[i]) {
                counts[i]++;
            }
        }
    }
    
    return counts;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* result = solution(nums, size, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops - for each of n elements, we scan up to n elements to the right

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for variables, result array doesn't count toward space complexity

✓ Linear Space

98.3K Views

Medium Frequency

~35 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler