Counting inversions in a changing array

Question

You have an array A[] of size (1 ≤ N ≤ 10^5). For each of i = 0, 1, 2, ..., N - 1, we want to determine the number of inversions in the array if all entries greater than i are decreased to i.

An inversion is defined as two entries A[i] and A[j] where A[i] > A[j] and i < j.

Example:

A[] = {3, 2, 1, 5, 2, 0, 5}

i = 0: {0, 0, 0, 0, 0, 0, 0}   Inversions: 0
i = 1: {1, 1, 1, 1, 1, 0, 1}   Inversions: 5
i = 2: {2, 2, 1, 2, 2, 0, 2}   Inversions: 7
i = 3: {3, 2, 1, 3, 2, 0, 3}   Inversions: 10
i = 4: {3, 2, 1, 4, 2, 0, 4}   Inversions: 10
i = 5: {3, 2, 1, 5, 2, 0, 5}   Inversions: 10
i = 6: {3, 2, 1, 5, 2, 0, 5}   Inversions: 10

So your output would be:

I know how to find the number of inversions in an array through MergeSort in O(NlogN). However, if I was to explicitly generate every array for each value of i, it would be an O(N^2logN) algorithm which wouldn't pass in time.

One observation I made was that the inversions increase as i increases. This makes sense because when all entries are 0, there will be no inversions (as it is sorted), but as you keep increasing the maximum entry value, the entry can become larger than entries that previously were of the same value.

So you could start with an A[] with only 0s, and keep increasing i. You can use your answer for previous values of i to determine the answer for larger values of i. Still, if you scanned through each array you would still get an O(N^2) algorithm.

How can I solve this problem?

aeternalis1 aeternalis1 · Accepted Answer · 2020-03-28T00:06:11

I'll take a stab at this. We're going to consider queries in descending order, so from i = N-1, ..., down to 0. First of all, notice that when we're shrinking all A[j] > i to i, any A[j] = i will no longer cause an inversion with elements larger than it of smaller index.

For example, say we have A = [1, 2, 5, 4] and we shrink A[2] to 4. Then we have A = [1, 2, 4, 4] and our single inversion disappears. Thus, for each j, we can count the number of elements in A with smaller index and larger value, and denote this V[j], the "number of inversions it contributes". We find the total number of inversions in the original array, and then for each i = N-1,...,0 we remove V[j] from the total number of inversions for all j such that V[j] = i.

Let's apply this to the example given.

A = [3, 2, 1, 5, 2, 0, 5]
V = [0, 1, 2, 0, 2, 5, 0]

Then, going through i = 6, 5, 4, 3, 2, 1:

i = 6: A = [3, 2, 1, 5, 2, 0, 5], res = 10 (original calculation using merge sort)
i = 5: A = [3, 2, 1, 5, 2, 0, 5], res = 10 (subtract nothing because V[3] = V[6] = 0)
i = 4: A = [3, 2, 1, 4, 2, 0, 4], res = 10 (subtract nothing because no occurrences of 4)
i = 3: A = [3, 2, 1, 3, 2, 0, 3], res = 10 (10 - V[0] = 10)
i = 2: A = [2, 2, 1, 2, 2, 0, 2], res = 7 (10 - V[1] - V[4] = 10 - 1 - 2 = 7)
i = 1: A = [1, 1, 1, 1, 1, 0, 1], res = 5 (7 - V[2] = 7 - 2 = 5)
i = 0: A = [0, 0, 0, 0, 0, 0, 0], res = 0 (5 - V[5] = 5 - 5 = 0)

And we get our desired outputs. Implementation details can vary; you can find the number of elements greater than A[j] with lower index using a Fenwick Tree or something similar. This algorithm runs in O(NlogN) time.

Counting inversions in a changing array

1 Answers