Count of Smaller Numbers After Self

Problem Statement

Given an integer array nums, return an integer array counts where counts[i] is the number of smaller elements to the right of num[i].

LeetCode:

• https://leetcode.com/problems/count-of-smaller-numbers-after-self/description/

Examples

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 only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Example 2:

Input: nums = [-1]
Output: [0]

Example 3:

Input: nums = [-1,-1]
Output: [0,0]

Constraints:

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

• 1 ≤ nums.length ≤ 10^5:
  • The size of the array can be very larger (up to 100,000).
  • Brute Force (O(n^2)), where you loop through all elements after i, will TLE (Time Limit Exceeded).
  • You need an efficient solution: O(n log n) is ideal.
• -10^4 ≤ nums[i] ≤ 10^4:
  • Elements are bounded integers.

Different Approaches

1️⃣ Brute Force Approach

🧠 Intuition:

For each element, scan all elements to its right and count how many are smaller.

💡 Approach:

• Loop through each element.
• For each, run a nested loop to its right.
• Count how many are smaller.

Code:

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n, 0);

        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[j] < nums[i])
                    result[i]++;
            }
        }
        return result;
    }
};

Complexity Analysis:

• Time Complexity:O(n^2)
• Space Complexity:O(1)

2️⃣ Modified Binary Search

Code:

class Solution {
public:

    // This function merges two sorted halves and counts the number of smaller elements after each element
    void merge(vector<pair<int, int>>& nums, vector<int>& count, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        vector<pair<int, int>> temp;

        // Merge the two sorted halves
        while (i <= mid && j <= right) {
            if (nums[i].first <= nums[j].first){
                // Element at j is not smaller, just add to temp
                temp.push_back(nums[j++]);
            } else {
                // Element at i is greater than nums[j]
                // So nums[i] has (right - j + 1) smaller elements to its right
                count[nums[i].second] += (right - j + 1);
                temp.push_back(nums[i++]);
            }
        }

        // Append remaining elements from the left half
        while (i <= mid) {
            temp.push_back(nums[i++]);
        }

        // Append remaining elements from the right half
        while (j <= right) {
            temp.push_back(nums[j++]);
        }

        // Copy merged elements back to the original `nums` vector
        for (int k = 0; k < temp.size(); k++) {
            nums[left + k] = temp[k];
        }
    }

    // Recursive merge sort with counting
    void sort(vector<pair<int, int>>& nums, vector<int>& count, int left, int right) {
        if (left < right) {
            int mid = (left + (right - left) / 2);

            // Sort left half
            sort(nums, count, left , mid);

            // Sort right half
            sort(nums, count, mid + 1, right);

            // Merge both halves and count inversions
            merge(nums, count, left, mid, right);
        }
    }

    // Main function
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();

        // Pair each element with its original index
        vector<pair<int, int>> arr(n);
        for (int i = 0; i < n; i++) {
            arr[i] = {nums[i], i};
        }

        // Result array to store counts
        vector<int> count(n, 0);

        // Perform modified merge sort
        sort(arr, count, 0, n - 1);

        return count;
    }
};

Complexity Analysis:

• Time Complexity:O(n log n)
  • The array is divided into two halves recursively, O(log n)
  • At each level, merging takes O(n) time (since every element is visited once per level).
  • During the merge step, we also count the number of smaller elements, which takes constant time per element.
• Space Complexity:O(n)
  • count vector stores the count of smaller elements of size n.
  • temp vector is used during merging up to size n.
  • arr vector of pairs of size n.