DiffPush Tier Arrays · Hard O(n log n) · O(n)
A monitoring pipeline pairs each sample with every later sample and flags the pair when the earlier reading is more than twice the later one, which indicates a sensor drifting far out of scale. The audit needs the total number of such flagged pairs in the stream.
Input: An array nums of n integers, one sensor reading per sample.
Output: The number of index pairs (i, j) with i < j and nums[i] > 2 * nums[j].
1 <= n <= 5 * 10^4-2^31 <= nums[i] <= 2^31 - 1Doubling a reading may overflow a 32-bit integerInput: {"nums":[1,3,2,3,1]}
Output: 2
Both 3s at positions 1 and 3 exceed twice the trailing 1 at position 4, giving two flagged pairs.
Input: {"nums":[2,4,3,5,1]}
Output: 3
The readings 4, 3 and 5 each outstrip twice the final tiny reading 1, so three pairs are flagged.