Back to DSA

Merge Sort - Count Inversions

hard
Acceptance: 38%
SortingDivide and Conquer

An inversion in an array is any pair of indices (i, j) with i < j where the earlier element is larger than the later one. Given an integer array, count the total number of inversions.

Examples

Example 1:
Input:nums = [3,1,2,5,4]
Output:3
Example 2:
Input:nums = [4,3,2,1]
Output:6

Hints

Related Problems

Top K Frequent ElementsmediumKth Largest Element in an ArraymediumMerge K Sorted ListshardSort ColorsmediumMeeting Rooms IImedium
00:00
class Solution {
    public int countInversions(int[] arr) {
        return mergeSort(arr, 0, arr.length - 1);
    }

    private int mergeSort(int[] arr, int l, int r) {
        if (l >= r) return 0;
        int mid = l + (r - l) / 2;
        int count = mergeSort(arr, l, mid) + mergeSort(arr, mid + 1, r);
        int[] temp = new int[r - l + 1];
        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r) {
            if (arr[i] <= arr[j]) temp[k++] = arr[i++];
            else { temp[k++] = arr[j++]; count += mid - i + 1; }
        }
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= r) temp[k++] = arr[j++];
        System.arraycopy(temp, 0, arr, l, temp.length);
        return count;
    }
}
Time complexityO(n log n)
Space complexityO(n)