We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Reverse Pairs

Number: 493

Difficulty: Hard

Paid? No

Companies: Google, Amazon, Meta, Microsoft, Apple

Problem Description

Given an integer array nums, count the number of reverse pairs in the array. A reverse pair is defined as a pair (i, j) where 0 <= i < j < nums.length and nums[i] > 2 * nums[j].

Key Insights

  • The brute force solution checks every possible pair, resulting in O(n^2) time complexity, which is too slow for the given constraints.
  • A modified merge sort can be used to both sort the array and count reverse pairs efficiently.
  • During the merge process, since the two halves are sorted, a two-pointer technique can efficiently count how many numbers in the right half satisfy the reverse pair condition for each number in the left half.
  • Alternative approaches include Binary Indexed Trees or Segment Trees, but merge sort provides a clean divide and conquer solution.

Space and Time Complexity

Time Complexity: O(n log n) – Each level of the merge sort takes O(n) time and there are O(log n) levels. Space Complexity: O(n) – Additional space is required for the temporary array during merging.

Solution

We solve the problem using a modified merge sort. The idea is to recursively split the array into halves, count reverse pairs in each half, and then count reverse pairs across the two halves before merging them. When merging two sorted halves, a two-pointer approach can be used to count the reverse pairs quickly. After counting, the two halves are merged in sorted order.

Code Solutions

# Define the Solution class
class Solution:
    def reversePairs(self, nums):
        # Helper function that uses merge sort to count reverse pairs
        def merge_sort(left, right):
            # Base case: if the segment has one or no elements, no reverse pairs exist
            if left >= right:
                return 0
            mid = (left + right) // 2
            # Count reverse pairs in the left and right halves
            count = merge_sort(left, mid) + merge_sort(mid+1, right)
            j = mid + 1
            # Count the reverse pairs: for every element in left half, 
            # move pointer j in right half until condition fails
            for i in range(left, mid+1):
                while j <= right and nums[i] > 2 * nums[j]:
                    j += 1
                count += j - (mid + 1)
            # Merge the two sorted halves
            temp = []
            p1, p2 = left, mid+1
            while p1 <= mid and p2 <= right:
                if nums[p1] <= nums[p2]:
                    temp.append(nums[p1])
                    p1 += 1
                else:
                    temp.append(nums[p2])
                    p2 += 1
            while p1 <= mid:
                temp.append(nums[p1])
                p1 += 1
            while p2 <= right:
                temp.append(nums[p2])
                p2 += 1
            # Copy the sorted elements back into the original array
            nums[left:right+1] = temp
            return count

        return merge_sort(0, len(nums)-1)
← Back to All Questions