dsa · hard
Backlog Overtakes
Stations report readings, a list of integers. A reading at an earlier index **overtakes** a later one when it is strictly more than **twice** the later reading. Count all overtaking pairs (i, j) with i < j and readings[i] > 2 * readings[j], and return the count.
Arguments
readings— the station readings in report order
Example
readings = [1,3,2,3,1]
Check each earlier index: 1 overtakes nothing. 3 (index 1) overtakes 1 (index 4) since 3 > 2. 2 (index 2) overtakes nothing (2 > 2 is false). 3 (index 3) overtakes 1 (index 4). Answer 2.
readings = [2,4,3,5,1] → 4 overtakes 1; 3 overtakes 1; 5 overtakes 1; also 4 overtakes... only 1. Answer 3.
Constraints
1 <= readings.length <= 10^5 -2 * 10^9 <= readings[i] <= 2 * 10^9 Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.
Examples
Example 1
Input: [1,3,2,3,1] Expected: 2
Example 2
Input: [2,4,3,5,1] Expected: 3
Example 3
Input: [5] Expected: 0