Arrays and Hashing Counting during merge sort
86. Reverse Pairs
You are given an array of integers nums. Count the pairs of positions (i, j) with i < j where the
earlier value is more than double the later one, that is, nums[i] > 2 × nums[j].
The order matters: nums[i] must come before nums[j] in the array. "More than double" is strict, so a
value that is exactly twice the later one does not count. The rule applies to negative numbers as written.
Example 1
Input: nums = [6, 2, 5, 1, 3]
3Explanation: Three pairs count: 6 before 2, 6 before 1, and 5 before 1. The pair 6 before 3 does not count, because 6 is exactly twice 3, not more.
Example 2
Input: nums = [-5, -3, 0]
1Explanation: Twice -3 is -6, and -5 is larger than -6, so -5 before -3 counts even though -5 is the smaller number. Twice 0 is 0, and neither -5 nor -3 is larger than 0.
Example 3
Input: nums = [2147483647, 1073741824]
0Explanation: Twice 1073741824 is 2147483648, which is one more than 2147483647. So the earlier value is not more than double the later one.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 105-231 ≤ nums[i] ≤ 231 − 1
Clarifying questions
What you would ask an interviewer before writing any code.