Reverse Pairs

Reverse Pairs

What is this problem about?

The Reverse Pairs interview question asks you to count the number of important reverse pairs in an integer array. A pair (i, j) is an important reverse pair if i < j and nums[i] > 2 * nums[j]. This is a variation of the classic counting inversions problem with a stricter condition. The challenge is doing this efficiently — O(n log n) — rather than the O(n^2) brute-force approach.

Why is this asked in interviews?

This HARD problem is asked at Apple, Microsoft, Meta, Amazon, Google, Bloomberg, and Adobe because it tests knowledge of advanced sorting techniques used for counting problems: merge sort, binary indexed trees (Fenwick trees), and segment trees. The problem is a direct extension of "Count Inversions" — a fundamental algorithm in competitive programming and used in ranking systems, recommendation engines, and data analysis.

Algorithmic pattern used

The primary pattern is modified merge sort. During the merge step, for each element in the right half, count how many elements in the left half satisfy nums[left] > 2 * nums[right]. Use a two-pointer approach within the merge step: since both halves are sorted, once nums[left] > 2 * nums[right], all subsequent left elements also satisfy the condition. Count them and advance the right pointer. Then perform the normal merge. This achieves O(n log n) time.

Example explanation

Array: [1, 3, 2, 3, 1]

Merge sort splits into [1, 3] and [2, 3, 1]:

• During merge: check each right element against left elements.
• Right = 2: left elements > 2*2=4? None.
• Right = 3: left elements > 6? None.
• Right = 1: left elements > 2? 3 > 2 → count 1.

Also count from lower-level merges. Total = 2.

Common mistakes candidates make

• Using the condition nums[i] > 2 * nums[j] in the sort comparison, which corrupts the sort order — count pairs BEFORE sorting in the merge step.
• Confusing this with standard inversion count where the condition is simply nums[i] > nums[j].
• Overflow: 2 * nums[j] can overflow 32-bit integers — use 64-bit arithmetic.
• Not using a separate two-pointer pass for counting (doing it inline with merging causes O(n^2) degeneration).

Interview preparation tip

For the Reverse Pairs coding problem, the divide and conquer and merge sort interview pattern is the efficient approach. The key insight: counting and sorting are separate steps within the merge function. Practice implementing standard merge sort first, then add the counting step. Interviewers at Deloitte and Adobe may ask for the BIT-based solution as an alternative — know that a BIT on compressed values also gives O(n log n) and is worth mentioning as a follow-up.