DSA interview question

Reverse Pairs

Hard · Algorithms · Topics: array, divide and conquer, merge sort

The problem

A price-monitoring service flags suspicious drops: for a series of daily prices, a reverse pair is two days i < j where the earlier price is more than double the later one (nums[i] > 2 × nums[j]). The analytics team needs the total count for long histories. Checking all pairs is O(n²). This is a close cousin of counting inversions, and the same merge-sort framework works, with one twist: the pairs are counted in a separate pass before merging, because the condition a > 2b doesn't line up with the merge's a > b comparison.

Example: [1, 3, 2, 3, 1] → 2 (the pairs (3, 1) at indices 1, 4 and 3, 4).

Function signature

long long reversePairs(vector<int> nums);  // pairs i < j with nums[i] > 2 * nums[j]

Test cases

Input `nums`	Output	Explanation
`[1, 3, 2, 3, 1]`	2	3 > 2·1 twice
`[2, 4, 3, 5, 1]`	3	(4,1), (3,1), (5,1)
`[5, 4, 3, 2, 1]`	4	(5,2), (5,1), (4,1), (3,1)
`[2147483647 ×6]`	0	2 × INT_MAX overflows an int; the comparison must use 64-bit
`[-5, -5]`	1	-5 > 2·(-5) = -10
`[1]`	0

(Confirm: values span the full int range, including negatives; compute 2 × nums[j] in 64 bits.)

How interviewers phrase it

"Count the reverse pairs: i < j and nums[i] > 2 × nums[j]" (LeetCode 493, Hard).
Usually asked right after "count inversions", to see whether you can adapt the merge-sort technique.

Clarifying questions to ask

Is it strictly greater than twice?
Can values be negative or near INT_MAX? (Overflow of 2 × nums[j].)
How large is n? (O(n log n) is expected.)

Follow-ups to expect

"Why not count during the merge, like inversions?"
"Why does the counting pass stay linear?"
"Where can overflow bite?"
"Other approaches?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview