Count of Smaller Numbers After Self LeetCode Solution

Last updated on January 21st, 2025 at 02:18 am

Here, we see a Count of Smaller Numbers After Self LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Binary Indexed Tree, Binary Search, Divide and Conquer, Segment Tree, Sort

Companies

Google

Level of Question

Hard

Count of Smaller Numbers After Self LeetCode Solution

Count of Smaller Numbers After Self LeetCode Solution

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

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Merge Sort with Counting” or “Binary Indexed Tree (BIT)-like Counting”. The problem involves counting the number of smaller elements to the right of each element in the array, which is achieved using divide-and-conquer (merge sort) or binary search-based insertion.

3. Code Implementation in Different Languages

3.1 Count of Smaller Numbers After Self C++

class Solution {
public:
    void merge(int left, int mid, int right, vector<pair<int, int>>& arr,vector<int>& count)
    {
        vector<pair<int, int>> temp(right - left + 1);
        int i = left;
        int j = mid + 1;
        int k = 0;
        while(i <= mid && j <= right)
        {
            if(arr[i].first <= arr[j].first)
            {
                temp[k++] = arr[j++]; 
            }
            else
            {
                count[arr[i].second] += (right - j + 1);
                temp[k++] = arr[i++];
            }
        }
        while(i <= mid)
        {
            temp[k++] = arr[i++];
        }
        while(j <= right)
        {
            temp[k++] = arr[j++];
        }
        for(int l = left; l <= right; l++)
        arr[l] = temp[l - left];
    }        
    void mergeSort(int left, int right, vector<pair<int, int>>& arr, vector<int>& count)
    {
        if(left >= right)
        {
            return;
        }
        int mid = left + (right - left) / 2;
        mergeSort(left, mid, arr, count);
        mergeSort(mid + 1, right, arr, count);
        merge(left, mid, right, arr, count);
    }
	vector<int> countSmaller(vector<int>& nums) {
        int n=nums.size();
	    vector<pair<int, int>> arr;
	    for(int i = 0; i < n; i++)
	    {
	        arr.push_back({nums[i], i});
	    }
	    vector<int> count(n, 0);
	    mergeSort(0, n - 1, arr, count);
	    return count;
	}
};

3.2 Count of Smaller Numbers After Self Java

class Solution {
    class Node {
        Node left, right;
        int val, sum, dup = 1;
        public Node(int v, int s) {
            val = v;
            sum = s;
        }
    }
    public List<Integer> countSmaller(int[] nums) {
        Integer[] ans = new Integer[nums.length];
        Node root = null;
        for (int i = nums.length - 1; i >= 0; i--) {
            root = insert(nums[i], root, ans, i, 0);
        }
        return Arrays.asList(ans);
    }
    private Node insert(int num, Node node, Integer[] ans, int i, int preSum) {
        if (node == null) {
            node = new Node(num, 0);
            ans[i] = preSum;
        } else if (node.val == num) {
            node.dup++;
            ans[i] = preSum + node.sum;
        } else if (node.val > num) {
            node.sum++;
            node.left = insert(num, node.left, ans, i, preSum);
        } else {
            node.right = insert(num, node.right, ans, i, preSum + node.dup + node.sum);
        }
        return node;
    }
}

3.3 Count of Smaller Numbers After Self JavaScript

var countSmaller = function(nums) {
    let sorted = [], result = [];
    for (let i=nums.length-1;i>=0;i--) {
        let left = 0, right = sorted.length;
        while(left < right) {
            let mid = left + Math.floor((right-left)/2);
            if (nums[i] > sorted[mid]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        result.unshift(left);
        sorted.splice(left, 0, nums[i]);
    }
    return result;
}

3.4 Count of Smaller Numbers After Self Python

class Solution(object):
    def countSmaller(self, nums):
        def sort(enum):
            half = len(enum) / 2
            if half:
                left, right = sort(enum[:half]), sort(enum[half:])
                for i in range(len(enum))[::-1]:
                    if not right or left and left[-1][1] > right[-1][1]:
                        smaller[left[-1][0]] += len(right)
                        enum[i] = left.pop()
                    else:
                        enum[i] = right.pop()
            return enum
        smaller = [0] * len(nums)
        sort(list(enumerate(nums)))
        return smaller

4. Time and Space Complexity

Time ComplexitySpace Complexity
C++O(n log n)O(n)
JavaO(n log n)O(n)
JavaScriptO(n2)O(n)
PythonO(n log n)O(n)
  • C++ and Python use the Merge Sort approach, which is efficient with O(n log n) time complexity.
  • Java uses a Binary Search Tree, which also achieves O(n log n) on average but may degrade to O(n^2) in the worst case if the tree becomes unbalanced.
  • JavaScript uses a Modified Binary Search with insertion into a sorted array, which is less efficient with O(n^2) time complexity due to the cost of maintaining the sorted array.
  • All implementations require O(n) space for auxiliary data structures (temporary arrays, trees, or sorted lists).
Scroll to Top