How Many Numbers Are Smaller Than the Current Number

How Many Numbers Are Smaller Than the Current Number - Problem

Given an array nums, for each nums[i] find out how many numbers in the array are smaller than it.

That is, for each nums[i] you have to count the number of valid j's such that j != i and nums[j] < nums[i].

Return the answer in an array.

Input & Output

Example 1 — Basic Case

$ Input: nums = [8,2,6,7,1,3]

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

💡 Note: For 8: numbers 2,6,7,1,3 are smaller → count=4. For 2: only 1 is smaller → count=1. For 6: numbers 2,1,3 are smaller → count=3. For 7: numbers 2,6,1,3 are smaller → count=3. For 1: no numbers are smaller → count=0. For 3: numbers 2,1 are smaller → count=2.

Example 2 — Duplicate Values

$ Input: nums = [6,5,4,8]

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

💡 Note: For 6: numbers 5,4 are smaller → count=2. For 5: only 4 is smaller → count=1. For 4: no numbers are smaller → count=0. For 8: numbers 6,5,4 are smaller → count=3.

Example 3 — All Same Values

$ Input: nums = [7,7,7,7]

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

💡 Note: All elements are equal, so no element is smaller than any other element. Each count is 0.

Constraints

2 ≤ nums.length ≤ 500
0 ≤ nums[i] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array with elements to analyze

Count Smaller

For each element, count how many are smaller

Result Array

Array of counts corresponding to input positions

Key Takeaway

🎯 Key Insight: For each element, count how many other elements in the array are smaller than it

Asked in

a Amazon 15 M Microsoft 12 Apple 8

The key insight is to count how many elements are smaller than each element. The brute force approach compares each element with all others in O(n²) time. The optimal sorting approach sorts the array first, then uses binary search to find positions efficiently in O(n log n) time, O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Sort with Index Mapping	O(n log n)	O(n)	Sort array while tracking original indices, then use sorted positions to count
Frequency Counting	O(n²)	O(n)	Count frequency of each number, then sum frequencies of smaller numbers
Brute Force	O(n²)	O(1)	For each element, compare with all other elements to count smaller ones

Sort with Index Mapping — Algorithm Steps

Create (value, index) pairs
Sort pairs by value
For each original element, find count in sorted array
Handle duplicates by finding first occurrence

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Array

Create sorted copy of the array

Binary Search

For each element, find its position in sorted array

Count Result

Position gives count of smaller elements

Code -

solution.c — C

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

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int* solution(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;
    int* result = (int*)malloc(numsSize * sizeof(int));
    
    // Create sorted copy
    int* sortedNums = (int*)malloc(numsSize * sizeof(int));
    for (int i = 0; i < numsSize; i++) {
        sortedNums[i] = nums[i];
    }
    qsort(sortedNums, numsSize, sizeof(int), compare);
    
    for (int i = 0; i < numsSize; i++) {
        // Binary search for first position where element >= nums[i]
        int left = 0, right = numsSize;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (sortedNums[mid] < nums[i]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        result[i] = left;
    }
    
    free(sortedNums);
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[100];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token) {
        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 log n)

Sorting the array takes O(n log n), then O(n) to build result

⚡ Linearithmic

Space Complexity

O(n)

Need extra space for sorted pairs and result array

⚡ Linearithmic Space

125.0K Views

Medium Frequency

~15 min Avg. Time

2.8K 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

Sort with Index Mapping — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler