Getting everything ready for you…

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

0s

Practice › Arrays

Reverse Pairs

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

Count the pairs (i, j) with i < j and a[i] > 2 · a[j].

Input

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

Output

The number of reverse pairs.

Constraints

Merge sort: before merging two sorted halves, count for each element of the left half how many right-half elements are less than half of it (two pointers). Use 64-bit arithmetic for 2·a[j].

Example 1

Input

5
1 3 2 3 1

Output

2

Example 2

Input

5
2 4 3 5 1

Output

3

Hints

  1. The O(n²) double loop is too slow for n = 5·10^4.
  2. During merge sort, both halves are sorted. For each left element, a pointer into the right half that only moves forward counts how many right elements satisfy a[i] > 2·a[j].

Approach

Modified merge sort, like counting inversions. In sort(l, r): sort both halves recursively, then — before merging — count cross pairs. Because both halves are sorted, as i moves right through the left half, the number of j in the right half with a[i] > 2·a[j] can only grow, so one pointer j sweeps the right half once. Then merge normally. Use 64-bit for 2·a[j] (values reach ±2^31).

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

Solution

C++ solution

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

vector<long long> a, tmp;

long long solve(int l, int r) {
    if (r - l <= 1) return 0;
    int m = (l + r) / 2;
    long long cnt = solve(l, m) + solve(m, r);
    int j = m;
    for (int i = l; i < m; i++) {
        while (j < r && a[i] > 2 * a[j]) j++;
        cnt += j - m;
    }
    merge(a.begin() + l, a.begin() + m, a.begin() + m, a.begin() + r, tmp.begin() + l);
    copy(tmp.begin() + l, tmp.begin() + r, a.begin() + l);
    return cnt;
}

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

Python solution

import sys


def solve(a):
    if len(a) <= 1:
        return a, 0
    m = len(a) // 2
    left, c1 = solve(a[:m])
    right, c2 = solve(a[m:])
    cnt, j = c1 + c2, 0
    for x in left:
        while j < len(right) and x > 2 * right[j]:
            j += 1
        cnt += j
    merged, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged += left[i:] + right[j:]
    return merged, cnt


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

Java solution

import java.util.*;
import java.io.*;

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

    static long solve(int l, int r) {
        if (r - l <= 1) return 0;
        int m = (l + r) / 2;
        long cnt = solve(l, m) + solve(m, r);
        int j = m;
        for (int i = l; i < m; i++) {
            while (j < r && a[i] > 2 * a[j]) j++;
            cnt += j - m;
        }
        int i = l, k = l;
        j = m;
        while (i < m && j < r) tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
        while (i < m) tmp[k++] = a[i++];
        while (j < r) tmp[k++] = a[j++];
        System.arraycopy(tmp, l, a, l, r - l);
        return cnt;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        StringTokenizer st = new StringTokenizer(br.readLine());
        a = new long[n];
        tmp = new long[n];
        for (int i = 0; i < n; i++) a[i] = Long.parseLong(st.nextToken());
        System.out.println(solve(0, n));
    }
}

Solve Reverse Pairs online · All practice problems