Number of subarrays with given inversions

Question

I recently failed to solve the following question during a programming contest -

Given an array ar[] containing n values, you need to find the number of subarrays which contains greater than or equal to k inversions.

Number of inversions in an array are defined as the number of pairs of indices (i,j) such that

1 <= i < j <= n and ar[i] > ar[j].

Worst case complexity of O(nlogn) was expected.

The pseudocode given there is not correct in my opinion, the logic is based on the pseudocode.They used a Binary Indexed Tree which can only give count of numbers less than a given number. — LTim

Matt Timmermans Matt Timmermans · Accepted Answer · 2015-12-29T19:29:54

You can do this in O(N log N) time:

Define (i,j) as a minimal subarray if there are at least K inversions in ar[i]...ar[j], AND less than K inversions in any shorter subarray that starts at i, i.e., if you remove an element the end of a minimal subarray, then it will have less than K inversions.

If (i,j) is a minimal subarray, then there are exactly N+1-j subarrays with at least K inversions that start at position i, because adding elements to the end never decreases the number of inversions. Furthermore, if there are any subarrays with >= K inversions that start at i, then there is exactly one minimal subarray that starts at i.

So all we have to do is find the minimal subarrays at every position, if they exist, and add up the corresponding total numbers of subarrays, like this (in pseudocode):

let total=0;
let i,j=1,1;
while(i<=N)
{
    while (j<i || inversions in ar[i]...ar[j] < K)
    {
        ++j;
        if (j>N)
        {
            return total; //out of subarrays
        }
    }
    // (i,j) is now a minimal subarray
    total+=N+1-j

    ++i; //next start position

    //now, IF (i,j) has enough inversions, then it is STILL
    //minimal, because otherwise the previous subarray would not have
    //been minimal either
}

To meet our total complexity target, we need that inversions in ar[i]...ar[j] check to cost us at most O(log N) per iteration.

We can do that by keeping the subarray elements in a balanced search tree with a count in each node that remembers the total size of that node's subtree. We will add at most N elements to this tree as J increases from 1 to N, for a total cost of O(N log N). We will remove at most N elements from this tree as i increases from 1 to N, for a total cost of O(N log N).

Furthermore, when we add an element to the tree, the number of inversions in the subarray increases by the number of elements greater than the one we're adding, because the new element is at the end of the subarray. When we remove an element from the start of the subarray, the number of inversions decreases by the number of elements less than the one we add. Both of these numbers take O(log N) to determine, so we can keep track of the total amount of inversions in the subarray in O(N log N) time altogether.

Number of subarrays with given inversions

1 Answers