{x}
blog image

Count of Smaller Numbers After Self

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

Problem Description

The problem is to count the number of smaller elements to the right of each element in an integer array nums. The output is an array counts where counts[i] represents the number of smaller elements to the right of nums[i].

Solution 1: Using Binary Indexed Tree (BIT)

This solution leverages a Binary Indexed Tree (BIT) to efficiently count smaller elements. A BIT allows for quick updates and prefix sum queries.

Algorithm:

  1. Discretization: Create a sorted list of unique elements from nums. This maps the original values to ranks (indices), compressing the value range and improving efficiency.
  2. Reverse Iteration: Iterate through nums from right to left.
  3. BIT Update: For each element nums[i], find its rank x in the discretized list. Update the BIT at index x by incrementing its value by 1 (representing the presence of this element).
  4. BIT Query: Query the BIT for the prefix sum up to x - 1. This gives the count of smaller elements to the right of nums[i]. Append this count to the result array ans.
  5. Reverse the result: Reverse the ans array to match the original order of nums.

Time Complexity: O(N log N), where N is the length of nums. The discretization takes O(N log N) (sorting), and each BIT update and query takes O(log N). Space Complexity: O(N), to store the BIT and the discretized list.

Solution 2: Using Segment Tree

Similar to the BIT approach, a Segment Tree can be used to efficiently manage the counts.

Algorithm:

  1. Discretization: Similar to Solution 1, discretize the input nums to compress the value range.
  2. Reverse Iteration and Update: Iterate through nums from right to left. For each element nums[i], get its rank x and update the corresponding node in the segment tree, incrementing its count by 1.
  3. Query and Append: Query the segment tree for the range [1, x-1] to get the count of smaller elements to the right of nums[i], and append this count to ans.
  4. Reverse the result: Reverse ans to match the original input order.

Time Complexity: O(N log N), where N is the length of nums. Building the segment tree takes O(N), and each update and query takes O(log N). Space Complexity: O(N), to store the segment tree and discretized list.

Solution 3: Merge Sort

This is a divide-and-conquer approach that leverages the merging step of merge sort to count smaller elements efficiently.

Algorithm:

  1. Pair Creation: Create an array of Pair objects, each containing an element from nums and its original index.
  2. Recursive Merge Sort: Recursively sort the array using merge sort. During the merge step, count the number of smaller elements from the right subarray for each element in the left subarray.
  3. Store Counts: Update the count array to store the number of smaller elements to the right of each element.

Time Complexity: O(N log N) due to the merge sort. Space Complexity: O(N) for temporary arrays during merge sort.

Code Implementations

The code implementations for all three solutions (BIT, Segment Tree, Merge Sort) are provided in the problem description in Python, Java, C++, and Go. Refer to that section for detailed code snippets. The comments within the code further explain the logic and implementation details of each solution.