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.

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 |