hardArrays & HashingPure DSA~50 min
Count Cheaper Later Listings
Listings arrive in a price feed in order. For each listing, analytics needs to know how many later listings undercut it. Compute, for every position, the count of strictly smaller values appearing after it.
Problem
Given an integer array nums, return an array counts where counts[i] is the number of elements to the right of nums[i] that are strictly smaller than nums[i].
Input
An array nums of n integers (1 ≤ n ≤ 10^5, −10^4 ≤ nums[i] ≤ 10^4).
Output
An array counts of the same length.
Constraints
- 1 ≤ n ≤ 10^5
- Values may be negative
- Target O(n log n) time
Examples
Example 1
Input
nums = [5,2,6,1]
Output
[2,1,1,0]
Right-smaller counts: 5→{2,1}=2, 2→{1}=1, 6→{1}=1, 1→0.
Example 2
Input
nums = [-1,-1]
Output
[0,0]
No strictly smaller element follows either −1.