DSA problem
Reverse Pairs
Given an integer array nums, return the number of important reverse pairs. A reverse pair is a pair (i, j) where 0 <= i < j < nums.length and nums[i] > 2 * nums[j].
The brute-force approach checks every pair, costing O(n²) time, which is far too slow for the upper input bounds. The challenge is to count these pairs in O(n log n), which strongly hints at a divide-and-conquer technique built on top of a sorting algorithm — specifically, modified merge sort.
The key observation is that merge sort gives us, at every level, two halves that have just been sorted. Before merging, we can count the reverse pairs that span across the halves (where i is in the left half and j is in the right half) by sweeping two pointers: for each i in [lo..mid], advance a pointer j in [mid + 1..hi] while nums[i] > 2 * nums[j]. Because both halves are sorted, this sweep is total-linear across all i. The number of valid j positions for each i is added to a running count.
After counting, we perform the standard merge step to produce a sorted range. Recursion handles the within-half pairs at deeper levels. To prevent integer overflow when computing 2 * nums[j] — values can reach 2 * 10⁹ — we cast to a 64-bit integer (long in Java / C++, native int is fine in Python, number is safe in JS up to 2⁵³). Overall: O(n log n) time, O(n) space for the merge buffer.
Examples
nums = [1,3,2,3,1]2nums = [2,4,3,5,1]3nums = [5,4,3,2,1]4Constraints
- 1 <= nums.length <= 5 * 10^4
- -2^31 <= nums[i] <= 2^31 - 1
- The expression 2 * nums[j] may overflow 32-bit signed integers — use a 64-bit type for the comparison.
- Target time complexity is O(n log n).
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.