The “Reverse Pairs” problem is a popular and challenging interview question. In this blog, we\u2019ll explain the problem, walk you through both brute force and optimal solutions, and make everything easy to understand with code comments, dry runs, and clear explanations.<\/p>\n\n\n\n
Given an integer array Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n A reverse pair<\/strong> is a pair Example 1:<\/strong><\/p>\n\n\n\n Example 2:<\/strong><\/p>\n\n\n\n Constraints:<\/strong><\/p>\n\n\n\n Let\u2019s solve the problem in the most straightforward way:<\/p>\n\n\n\n This approach is easy to understand but not efficient for large arrays.<\/p>\n\n\n\nnums<\/code>, return the number of reverse pairs<\/strong> in the array<\/em>.<\/p>\n\n\n\n(i, j)<\/code> where:<\/p>\n\n\n\n\n
0 <= i < j < nums.length<\/code>\u00a0and<\/li>\n\n\n\nnums[i] > 2 * nums[j]<\/code>.<\/li>\n<\/ul>\n\n\n\nInput:<\/strong> nums = [1,3,2,3,1]
Output:<\/strong> 2
Explanation:<\/strong> The reverse pairs are:
(1, 4) --> nums[1] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) --> nums[3] = 3, nums[4] = 1, 3 > 2 * 1<\/pre>\n\n\n\nInput:<\/strong> nums = [2,4,3,5,1]
Output:<\/strong> 3
Explanation:<\/strong> The reverse pairs are:
(1, 4) --> nums[1] = 4, nums[4] = 1, 4 > 2 * 1
(2, 4) --> nums[2] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) --> nums[3] = 5, nums[4] = 1, 5 > 2 * 1<\/pre>\n\n\n\n\n
1 <= nums.length <= 5 * 104<\/sup><\/code><\/li>\n\n\n\n-231<\/sup> <= nums[i] <= 231<\/sup> - 1<\/code><\/li>\n<\/ul>\n\n\n
\n\n\n\nBrute Force Solution (Nested Loops)<\/h2>\n\n\n\n
Intuition and Approach<\/h3>\n\n\n\n
\n
For each element, compare it with every element that comes after it.<\/li>\n\n\n\n
If\u00a0nums[i] > 2 * nums[j]<\/code>, count it as a reverse pair.<\/li>\n\n\n\n
We check all possible pairs, so we count every reverse pair.<\/li>\n<\/ol>\n\n\n\nCode Implementation<\/h3>\n\n\n\n