Close Menu
    Code and Debug
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook X (Twitter) Instagram YouTube WhatsApp
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook Instagram YouTube LinkedIn WhatsApp
    Code and Debug – BlogCode and Debug – Blog
    Code and Debug – BlogCode and Debug – Blog
    Home»Data Structures & Algorithms»Reverse Pairs | Leetcode 493 | Optimal Merge Sort
    Data Structures & Algorithms

    Reverse Pairs | Leetcode 493 | Optimal Merge Sort

    codeanddebugBy codeanddebug7 July 2025No Comments5 Mins Read
    Share Facebook Twitter Pinterest LinkedIn Tumblr Reddit Telegram Email
    Featured image of question to reverse pairs on leetcode
    Share
    Facebook Twitter LinkedIn Pinterest Email

    The “Reverse Pairs” problem is a popular and challenging interview question. In this blog, we’ll 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.

    Given an integer array nums, return the number of reverse pairs in the array.

    Here’s the [Problem Link] to begin with.

    A reverse pair is a pair (i, j) where:

    • 0 <= i < j < nums.length and
    • nums[i] > 2 * nums[j].

    Example 1:

    Input: nums = [1,3,2,3,1]
    Output: 2
    Explanation: 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

    Example 2:

    Input: nums = [2,4,3,5,1]
    Output: 3
    Explanation: 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

    Constraints:

    • 1 <= nums.length <= 5 * 104
    • -231 <= nums[i] <= 231 - 1
    Contents:
     [show]
    • Brute Force Solution (Nested Loops)
      • Intuition and Approach
      • Code Implementation
      • Code Explanation
      • Dry Run
      • Time and Space Complexity
      • Conclusion
    • Optimal Solution (Merge Sort Approach)
      • Intuition and Approach
      • Code Implementation
      • Code Explanation
      • Dry Run
      • Time and Space Complexity
      • Conclusion
    • Final Thoughts

    Brute Force Solution (Nested Loops)

    Intuition and Approach

    Let’s solve the problem in the most straightforward way:

    1. Check Every Pair:
      For each element, compare it with every element that comes after it.
    2. Count Reverse Pairs:
      If nums[i] > 2 * nums[j], count it as a reverse pair.
    3. Why does this work?
      We check all possible pairs, so we count every reverse pair.

    This approach is easy to understand but not efficient for large arrays.

    Code Implementation

    from typing import List
    
    class Solution:
        def reversePairs(self, nums: List[int]) -> int:
            count = 0
            n = len(nums)
            for i in range(0, n):
                for j in range(i + 1, n):
                    if nums[i] > 2 * nums[j]:      # check reverse pair condition
                        count += 1
            return count
    Python

    Code Explanation

    • We use two nested loops.
    • For each pair (i, j) where i < j, we check if nums[i] > 2 * nums[j].
    • If true, we increment the reverse pair count.

    Dry Run

    Input:
    nums = [1][1]

    • (1,3): 1 > 6? No
    • (1,2): 1 > 4? No
    • (1,3): 1 > 6? No
    • (1,1): 1 > 2? No
    • (3,2): 3 > 4? No
    • (3,3): 3 > 6? No
    • (3,1): 3 > 2? Yes (count = 1)
    • (2,3): 2 > 6? No
    • (2,1): 2 > 2? No
    • (3,1): 3 > 2? Yes (count = 2)

    Final count:
    2

    Time and Space Complexity

    • Time Complexity: O(n^2)
      Two nested loops for all pairs.
    • Space Complexity: O(1)
      Only a counter variable is used.

    Conclusion

    The brute force approach is simple and good for understanding, but it’s too slow for large arrays.


    Optimal Solution (Merge Sort Approach)

    Intuition and Approach

    We can count reverse pairs much faster using a modified merge sort:

    1. Divide and Conquer:
      Use merge sort to divide the array into smaller parts.
    2. Count Reverse Pairs During Merge:
      While merging two sorted halves, for each element in the left half, count how many elements in the right half satisfy the reverse pair condition.
    3. Why does this work?
      Merge sort naturally compares and sorts elements, so it’s efficient to count reverse pairs during the merge step.

    This approach is efficient and works well for large arrays.

    Code Implementation

    from typing import List, Tuple
    
    class Solution:
        def mergeList(self, arr1: List[int], arr2: List[int]) -> Tuple[List[int], int]:
            n = len(arr1)
            m = len(arr2)
            count = 0
            result = []
            j = 0
            # Count reverse pairs
            for i in range(0, n):
                while j < m and arr1[i] > 2 * arr2[j]:
                    j += 1
                count += j
    
            i, j = 0, 0
            # Merge two sorted arrays
            while i < n and j < m:
                if arr1[i] <= arr2[j]:
                    result.append(arr1[i])
                    i += 1
                else:
                    result.append(arr2[j])
                    j += 1
    
            while i < n:
                result.append(arr1[i])
                i += 1
            while j < m:
                result.append(arr2[j])
                j += 1
    
            return result, count
    
        def mergeSort(self, lst: List[int]) -> Tuple[List[int], int]:
            if len(lst) <= 1:
                return lst, 0
    
            mid = len(lst) // 2
            first_half = lst[:mid]
            second_half = lst[mid:]
    
            fh, cnt1 = self.mergeSort(first_half)
            sh, cnt2 = self.mergeSort(second_half)
    
            merged, count = self.mergeList(fh, sh)
            return merged, cnt1 + cnt2 + count
    
        def reversePairs(self, nums: List[int]) -> int:
            m, c = self.mergeSort(nums)
            return c
    Python

    Code Explanation

    • We use a modified merge sort.
    • During the merge step, for each element in the left half, we count how many elements in the right half satisfy arr1[i] > 2 * arr2[j].
    • We merge the two halves as in standard merge sort.
    • We sum up the counts from all recursive calls.

    Dry Run

    Input:
    nums = [1][1]

    • Split into [1] and [1]
    • [1] → [1], “
    • [1] → , `[1]` → , [1]
    • Merge “ and [1]: check 3 > 2*1? Yes (count = 1)
    • Merge “ and [1]: check 2 > 21? No; 2 > 23? No
    • Merge [1] and [1]: count reverse pairs across the two halves
    • Total count = 2

    Time and Space Complexity

    • Time Complexity: O(n log n)
      Merge sort divides and merges arrays efficiently.
    • Space Complexity: O(n)
      Extra space is used for temporary arrays during merge.

    Conclusion

    The optimal solution is efficient and works well for large arrays. It’s the best approach for interviews and practical use.

    Final Thoughts

    The “Reverse Pairs” problem is a great example of how to optimize from brute force to an efficient divide-and-conquer solution. Start with brute force to understand the basics, then use the merge sort approach for best performance.

    Join our Advance DSA COURSE

    For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.

    Array Hard Sorting Algorithm
    Share. Facebook Twitter Pinterest LinkedIn Tumblr Email
    Previous ArticleCount Inversions – GeeksforGeeks Solution Explained
    codeanddebug
    • Website

    Related Posts

    Data Structures & Algorithms

    Count Inversions – GeeksforGeeks Solution Explained

    7 July 2025
    Data Structures & Algorithms

    Missing And Repeating – GeeksforGeeks Solution Explained

    7 July 2025
    Data Structures & Algorithms

    Merge Without Extra Space – GeeksforGeeks Solution Explained

    7 July 2025
    Add A Comment
    Leave A Reply Cancel Reply

    Categories
    • Data Structures & Algorithms (99)
      • Beginner (44)
      • Expert (28)
      • Intermediate (27)
    • Uncategorised (1)
    Recent Posts

    Reverse Pairs | Leetcode 493 | Optimal Merge Sort

    7 July 2025

    Count Inversions – GeeksforGeeks Solution Explained

    7 July 2025

    Missing And Repeating – GeeksforGeeks Solution Explained

    7 July 2025

    Merge Without Extra Space – GeeksforGeeks Solution Explained

    7 July 2025

    Merge Intervals | Leetcode 56 | Brute Force and Optimal

    7 July 2025
    Facebook Instagram YouTube LinkedIn WhatsApp
    © 2025 Code and Debug. All rights reserved.

    Type above and press Enter to search. Press Esc to cancel.