Count of Smaller Numbers After Self

HARD

Description

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]

Constraints:

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

Approaches

Checkout 4 different approaches to solve Count of Smaller Numbers After Self. Click on different approaches to view the approach and algorithm in detail.

Brute Force - Nested Loops

The most straightforward approach is to use nested loops. For each element at index i, we iterate through all elements to its right and count how many are smaller.

Algorithm

Initialize an empty result list
For each element at index i from 0 to n-1:
- Initialize count = 0
- For each element at index j from i+1 to n-1:
  - If nums[j] < nums[i], increment count
- Add count to result list
Return result list

For each element at position i, we iterate through all elements from position i+1 to the end of the array. We maintain a counter that increments whenever we find an element smaller than nums[i]. This counter becomes the result for position i.

public List<Integer> countSmaller(int[] nums) {
    List<Integer> result = new ArrayList<>();
    
    for (int i = 0; i < nums.length; i++) {
        int count = 0;
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] < nums[i]) {
                count++;
            }
        }
        result.add(count);
    }
    
    return result;
}

Complexity Analysis

Time Complexity: O(n²) - We have nested loops where outer loop runs n times and inner loop runs up to n timesSpace Complexity: O(1) - Only using constant extra space (not counting the result array)

Pros and Cons

Pros:

Simple and easy to understand
No extra space needed except for result
Works correctly for all cases

Cons:

Very slow for large inputs
Not scalable
Inefficient for the given constraints

Code Solutions

Checking out 3 solutions in different languages for Count of Smaller Numbers After Self. Click on different languages to view the code.

import java.util.ArrayList ; import java.util.Arrays ; import java.util.List ; public class Count_of_Smaller_Numbers_After_Self { public static void main ( String [] args ) { Count_of_Smaller_Numbers_After_Self out = new Count_of_Smaller_Numbers_After_Self (); Solution s = out . new Solution (); System . out . println ( s . countSmaller ( new int []{ 5 , 2 , 6 , 1 })); } class Solution { public List < Integer > countSmaller ( int [] nums ) { List < Integer > result = new ArrayList <>(); List < Integer > sorted = new ArrayList <>(); if ( nums == null || nums . length == 0 ) { return result ; } for ( int i = nums . length - 1 ; i >= 0 ; i --) { // binary search for current pos, reference: Arrays.binarySearch() int left = 0 ; int right = sorted . size (); while ( left < right ) { int mid = left + ( right - left ) / 2 ; if ( nums [ i ] <= sorted . get ( mid )) { right = mid ; } else { left = mid + 1 ; } } // now nums[i] should be placed at index left sorted . add ( left , nums [ i ]); // @note: equal to .insert() result . add ( 0 , left ); // @note: insert to 1st node，因为是倒序scan array } return result ; } } } ############ class Solution { public List < Integer > countSmaller ( int [] nums ) { Set < Integer > s = new HashSet <>(); for ( int v : nums ) { s . add ( v ); } List < Integer > alls = new ArrayList <>( s ); alls . sort ( Comparator . comparingInt ( a -> a )); int n = alls . size (); Map < Integer , Integer > m = new HashMap <>( n ); for ( int i = 0 ; i < n ; ++ i ) { m . put ( alls . get ( i ), i + 1 ); } BinaryIndexedTree tree = new BinaryIndexedTree ( n ); LinkedList < Integer > ans = new LinkedList <>(); for ( int i = nums . length - 1 ; i >= 0 ; -- i ) { int x = m . get ( nums [ i ]); tree . update ( x , 1 ); ans . addFirst ( tree . query ( x - 1 )); } return ans ; } } class BinaryIndexedTree { private int n ; private int [] c ; public BinaryIndexedTree ( int n ) { this . n = n ; c = new int [ n + 1 ]; } public void update ( int x , int delta ) { while ( x <= n ) { c [ x ] += delta ; x += lowbit ( x ); } } public int query ( int x ) { int s = 0 ; while ( x > 0 ) { s += c [ x ]; x -= lowbit ( x ); } return s ; } public static int lowbit ( int x ) { return x & - x ; } }

Video Solution

Watch the video walkthrough for Count of Smaller Numbers After Self

Algorithms:

Binary SearchDivide and ConquerMerge Sort

Data Structures:

ArrayBinary Indexed TreeSegment TreeOrdered Set

Companies:

Geico |