Count Reverse Pairs

Intuition

Count pairs (i,j) where i<j and A[i]>2*A[j]. Use merge sort: during merging, count pairs across left and right halves efficiently.

Algorithm

1Modified merge sort.
2Before merging, count pairs: for each element in left half, count elements in right half where left[i] > 2*right[j].
3Use two pointers on sorted halves for O(n) counting per level.
4Merge normally.

Common Pitfalls

•Count BEFORE merging (after recursive sort), so both halves are sorted. The count step is separate from the merge step.

Count Reverse Pairs.java

Java

// Approach: Modified merge sort. Before merging, count pairs (i,j) where arr[i] > 2*arr[j] with j in right half.
// Time: O(n log n) Space: O(n)
class Solution {
    public int countRevPairs(int[] arr) {
        int n = arr.length;
        int temp[] = new int[n];
        return divide(arr, temp, 0, n - 1);
    }

    static int divide(int arr[], int temp[], int low, int high) {
        int c = 0;
        if (low < high) {
            int mid = (low + high) / 2;
            c = c + divide(arr, temp, low, mid);
            c = c + divide(arr, temp, mid + 1, high);
            c = c + count(arr, temp, low, mid, high);
            mergeSort(arr, temp, low, mid, high);
        }

        return c;
    }

    static void mergeSort(int arr[], int temp[], int low, int mid, int high) {
        int left = low;
        int right = mid + 1;
        int k = low;
        while (left <= mid && right <= high) {
            if (arr[left] <= arr[right]) {
                temp[k] = arr[left];
                left++;
                k++;
            } else {
                temp[k] = arr[right];
                right++;
                k++;
            }
        }

        while (left <= mid) {
            temp[k] = arr[left];
            left++;
            k++;
        }

        while (right <= high) {
            temp[k] = arr[right];
            right++;
            k++;
        }

        for (int i = low; i <= high; i++)
            arr[i] = temp[i];
    }

    static int count(int arr[], int temp[], int low, int mid, int high) {
        int c = 0;
        int h = mid + 1;
        for (int i = low; i <= mid; i++) {
            while (h <= high && arr[i] > (2 * arr[h]))
                h++;
            c = c + h - (mid + 1);
        }

        return c;
    }
}

Was this solution helpful?