Count Earlier Values Greater Than Twice a Later Value
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
# Count Earlier Values Greater Than Twice a Later Value
Given `nums`, count the index pairs `(i, j)` satisfying both `i < j` and `nums[i] > 2 * nums[j]`.
The comparison is strict. Count pairs of positions, including positions holding equal values; do not count only distinct value pairs.
### Interface
`class Solution { public: int reversePairs(vector<int>& nums); };`
### Example 1
```text
Input: nums = [8,4,1]
Output: 2
```
The qualifying pairs are `(0,2)` and `(1,2)`, since 8 and 4 both exceed twice 1. Pair `(0,1)` does not qualify because 8 equals twice 4.
### Example 2
```text
Input: nums = [-5,-5]
Output: 1
```
There is one possible index pair, and `-5 > 2 * (-5)` is true. Equal negative values can therefore qualify.
### Constraints
- `1 <= nums.length <= 50000`.
- `-2147483648 <= nums[i] <= 2147483647`.
### What a Strong Answer Covers
- Original index order and the strict doubled-value comparison.
- Repeated and negative values, including signed integer extremes.
- Safe arithmetic for doubling and counting.
- A correctness argument and resource bounds for the full array length.
```hint Combining intervals
After counting pairs wholly inside two consecutive intervals, what pairs remain to be counted between them?
```
Overview: Count ordered index pairs whose earlier value strictly exceeds twice the later value, with duplicates, negatives and full signed 32-bit inputs.
