527. Big Reverse Pairs
A lab records daily measurements in nums. A pair of days (i, j) with i < j is called a big reversal when the earlier measurement is more than twice the later one, that is nums[i] > 2 * nums[j].
Return the number of big reversals in the array. Measurements can be negative or zero, and doubling can exceed the range of a 32-bit integer, so compare using 64-bit arithmetic. The constraints guarantee that the answer fits in a 32-bit signed integer.
Example 1
- Input:
- nums = [9,2,5,1,4]
- Output:
- 4
- Explanation:
The big reversals are (9,2), (9,1), (9,4) and (5,1), giving 4.
Example 2
- Input:
- nums = [-6,-1,3,-4]
- Output:
- 3
- Explanation:
The pairs (-6,-4), (-1,-4) and (3,-4) satisfy x > 2y (for example -6 > -8); no other pair does.
Constraints
1 ≤ nums.length ≤ 5 * 104
-231 ≤ nums[i] ≤ 231 - 1
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)