Reverse Pairs

For an array A, if i < j, and A [i] > A [j], called (A [i], A [j]) is a reverse pair.

return total of reverse pairs in A.

Example:

Given A = [2, 4, 1, 3, 5] , (2, 1), (4, 1), (4, 3) are reverse pairs. return 3.

Solution:

If we cut the array into two parts: [2,4] and [1,3,5]. We could easily find the reverse pairs during merge in Merge Sort. We sum the number of elements in front of a number who is ready to be pushed into sorted array in right segment during merge process. For example: the first number need to be pushed to sorted array is 1, and there are 2 numbers in left segment. Then the next number in right array is 3, and there a re only 1 number in left segment (4 now).

Code:

public class Solution {
    /**
     * @param A an array
     * @return total of reverse pairs
     */
    public long reversePairs(int[] A) {
        return mergeSort(A, 0, A.length - 1, new int[A.length]);
    }

    private long mergeSort(int[] A, int start, int end, int[] temp) {
        if (start >= end) {
            return 0;
        }
        int mid = start + (end - start) / 2;
        long sum = 0;
        sum += mergeSort(A, start, mid, temp);
        sum += mergeSort(A, mid + 1, end, temp);
        sum += merge(A, start, mid, end, temp);
        return sum;
    }

    private long merge(int[] A, int start, int mid, int end, int[] temp) {
        int left = start;
        int right = mid + 1;
        int index = start;
        int sum = 0;
        while (left <= mid && right <= end) {
            if (A[left] <= A[right]) {
                temp[index++] = A[left++];
            } else {
                temp[index++] = A[right++];
                sum += mid - left + 1;
            }
        }
        while (left <= mid) {
            temp[index++] = A[left++];
        }
        while (right <= end) {
            temp[index++] = A[right++];
        }
        for (int i = start; i <= end; i++) {
            A[i] = temp[i];
        }
        return sum;
    }
}