Reverse Pairs - Video Solutions

Problem Overview: Given an integer array nums, count pairs (i, j) such that i < j and nums[i] > 2 * nums[j]. The challenge is detecting these pairs efficiently without checking every combination.

Approach 1: Naive Brute Force (O(n²) time, O(1) space)

The straightforward solution checks every pair of indices. Use two nested loops: fix i, then iterate j from i + 1 to the end of the array. For each pair, test the condition nums[i] > 2 * nums[j] and increment a counter when it holds. This approach requires no additional data structures and is easy to implement in any language. However, the nested iteration results in quadratic time, which becomes too slow when the array size grows into tens of thousands. The brute force version mainly helps validate correctness or build intuition before implementing an optimized algorithm.

Approach 2: Optimized Merge Sort (O(n log n) time, O(n) space)

The optimal solution uses a modified merge sort with a divide and conquer strategy. While splitting the array into halves and sorting them, you also count valid reverse pairs across the two halves. Because each half is already sorted, you can efficiently detect pairs using a two-pointer scan before merging. For each element in the left half, advance a pointer in the right half while nums[i] > 2 * nums[j]. The number of valid indices skipped contributes to the reverse pair count.

After counting cross-half pairs, perform the standard merge step to combine the two sorted halves. Sorting during recursion guarantees that each level can count pairs in linear time. Since merge sort has log n levels and each level processes n elements, the overall complexity becomes O(n log n). This technique is closely related to counting inversions in arrays and frequently appears in problems involving ordered relationships.

Although other advanced solutions exist using a Binary Indexed Tree, segment tree, or ordered set, the merge sort approach is typically preferred because it is easier to implement and performs reliably across languages without requiring coordinate compression or additional indexing tricks.

Recommended for interviews: The optimized merge sort solution is the expected answer in most interviews. It demonstrates your understanding of divide-and-conquer counting techniques and how sorted subarrays enable faster pair detection. Starting with the brute force explanation shows clear reasoning, but implementing the O(n log n) merge sort solution proves you can optimize beyond quadratic scans.