Scale Engineer

Count of Smaller Numbers After Self

Hard
#0302Time: O(n²) - We have nested loops where outer loop runs n times and inner loop runs up to n timesSpace: O(1) - Only using constant extra space (not counting the result array)1 company
Algorithms
Binary SearchDivide and ConquerMerge Sort
Data structures
ArrayBinary Indexed TreeSegment TreeOrdered Set
Companies
Geico

Prompt

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 <= 105
  • -104 <= nums[i] <= 104

Approaches

4 approaches with complexity analysis and trade-offs.

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

Walkthrough

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

Time

O(n²) - We have nested loops where outer loop runs n times and inner loop runs up to n times

Space

O(1) - Only using constant extra space (not counting the result array)

Trade-offs

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

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem