Count of Smaller Numbers After Self
HardPrompt
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
Solution
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.