hardArrays & HashingPure DSA~45 min
Count Significant Later Drops
A metric is sampled over time. You want to count 'significant drop' pairs: an earlier sample whose value is more than double a strictly later sample — these flag steep declines worth investigating.
Problem
Given an integer array nums, return the number of important reverse pairs: index pairs (i, j) with i < j and nums[i] > 2 * nums[j].
Input
An integer array nums.
Output
The count of important reverse pairs.
Constraints
- 1 ≤ n ≤ 5e4
- -2^31 ≤ nums[i] ≤ 2^31 - 1
Examples
Example 1
Input
[1,3,2,3,1]
Output
2
Pairs (1,4): 3>2*1, and (3,4): 3>2*1.
Example 2
Input
[2,4,3,5,1]
Output
3
(1,4):4>2, (2,4):3>2, (3,4):5>2.