Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Arrays

Count Inversions

Hard · Arrays · Asked at Amazon, Microsoft, Google, Flipkart

An inversion is a pair (i, j) with i < j and a[i] > a[j]. Count the inversions.

Input

First line: n. Second line: n space-separated integers.

Output

The number of inversions.

Constraints

O(n²) is too slow for n = 10^5 — count inversions while doing merge sort. The answer can exceed 32-bit range.

Example 1

Input

5
2 4 1 3 5

Output

3

Example 2

Input

3
1 2 3

Output

0

Hints

  1. An inversion is a pair i < j with a[i] > a[j]. Checking all pairs is O(n²).
  2. Merge sort: while merging, if right[j] < left[i], then right[j] is smaller than every remaining left element.

Approach

Sort with merge sort and count during each merge. Both halves are sorted, so when the right element b[j] is taken before the left element a[i], it forms an inversion with a[i] and with every element after it in the left half: add (leftSize − i). Take from the left when the values are equal, because equal values aren't inversions. The total can reach about n²/2 ≈ 5 × 10^9, so use a 64-bit counter.

Complexity: O(n log n) time · O(n) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

long long sortCount(vector<long long> &a, vector<long long> &tmp, int lo, int hi) {
    if (hi - lo <= 1) return 0;
    int mid = (lo + hi) / 2;
    long long cnt = sortCount(a, tmp, lo, mid) + sortCount(a, tmp, mid, hi);
    int i = lo, j = mid, k = lo;
    while (i < mid && j < hi) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else {
            cnt += mid - i;
            tmp[k++] = a[j++];
        }
    }
    while (i < mid) tmp[k++] = a[i++];
    while (j < hi) tmp[k++] = a[j++];
    for (int t = lo; t < hi; t++) a[t] = tmp[t];
    return cnt;
}

int main() {
    int n;
    cin >> n;
    vector<long long> a(n), tmp(n);
    for (auto &x : a) cin >> x;
    cout << sortCount(a, tmp, 0, n) << "\n";
    return 0;
}

Python solution

import sys


def sort_count(a):
    if len(a) <= 1:
        return a, 0
    mid = len(a) // 2
    left, x = sort_count(a[:mid])
    right, y = sort_count(a[mid:])
    merged, cnt, i, j = [], x + y, 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            cnt += len(left) - i
            merged.append(right[j])
            j += 1
    merged += left[i:]
    merged += right[j:]
    return merged, cnt


data = list(map(int, sys.stdin.read().split()))
print(sort_count(data[1 : data[0] + 1])[1])

Java solution

import java.util.*;

public class Main {
    static long[] a, tmp;

    static long sortCount(int lo, int hi) {
        if (hi - lo <= 1) return 0;
        int mid = (lo + hi) / 2;
        long cnt = sortCount(lo, mid) + sortCount(mid, hi);
        int i = lo, j = mid, k = lo;
        while (i < mid && j < hi) {
            if (a[i] <= a[j]) tmp[k++] = a[i++];
            else {
                cnt += mid - i;
                tmp[k++] = a[j++];
            }
        }
        while (i < mid) tmp[k++] = a[i++];
        while (j < hi) tmp[k++] = a[j++];
        System.arraycopy(tmp, lo, a, lo, hi - lo);
        return cnt;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        a = new long[n];
        tmp = new long[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextLong();
        System.out.println(sortCount(0, n));
    }
}

Solve Count Inversions online · All practice problems