thesarfo

Reference

Count Reverse Pairs

Counting pairs where arr[i] > 2*arr[j] using a merge-sort-based counting step instead of nested loops.

views 0

Count pairs (i,j) where i < j and arr[i] > 2 * arr[j]. (LeetCode 493)

Brute force: check every pair directly — O(n²).

Optimal — merge sort with a counting step: merge sort naturally divides the array and sorts during merging. Before merging two already-sorted halves back together, count how many cross-pairs satisfy left > 2 * right — since both halves are sorted at that point, this can be done with a two-pointer sweep instead of nested loops.

public class Solution {
    private static void merge(int[] arr, int low, int mid, int high) {
        ArrayList<Integer> temp = new ArrayList<>();
        int left = low, right = mid + 1;


        while (left <= mid && right <= high) {
            if (arr[left] <= arr[right]) temp.add(arr[left++]);
            else temp.add(arr[right++]);
        }
        while (left <= mid) temp.add(arr[left++]);
        while (right <= high) temp.add(arr[right++]);


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


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


    private static int mergeSort(int[] arr, int low, int high) {
        if (low >= high) return 0;
        int mid = (low + high) / 2;


        int count = mergeSort(arr, low, mid);
        count += mergeSort(arr, mid + 1, high);
        count += countPairs(arr, low, mid, high);
        merge(arr, low, mid, high);


        return count;
    }


    public static int team(int[] skill, int n) {
        return mergeSort(skill, 0, n - 1);
    }
}

Time: O(n log n). Space: O(n).