For each number in an array, count how many later numbers are smaller than it.
Given an integer array nums, return an array counts where counts[i] is the number of elements to the right of index i that are strictly smaller than nums[i].
You must compute this value for every position in the array. The result for each index depends only on the suffix to its right, so a naive nested scan is usually too slow for large inputs. Think about how to maintain information about the numbers you have already seen while processing the array from right to left, or how to count smaller elements efficiently during a divide-and-conquer merge.
Input Format
- An integer array
nums. - Each position contains one integer value.
Output Format
- Return an integer array
countsof the same length asnums. counts[i]is the number of indicesj > isuch thatnums[j] < nums[i].
Constraints
1 <= nums.length- Values may be negative or positive.
- The answer for each position must be based on strictly smaller values only.
- Aim for better than time on large inputs.
Example 1
Input
nums = [5, 2, 6, 1]
Output
[2, 1, 1, 0]
Explanation
For 5, the smaller numbers to its right are 2 and 1. For 2, only 1 is smaller. For 6, only 1 is smaller. For 1, nothing is to its right.
Example 2
Input
nums = [3, 2, 2, 6, 1]
Output
[3, 1, 1, 1, 0]
Explanation
For the first 3, the smaller numbers to the right are 2, 2, and 1. For each 2, only 1 is smaller. For 6, only 1 is smaller.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.