LeetCode : K Inverse Pairs Array

Solution :

One of the strong heuristics that I generally use for solving counting problems in programming is that it is most likely a dynamic programming problem and most of the cases it is true, since most such counting problems can be defined recursively. In this problem, of counting the number of k-inverse pairs in an array of size 'n' (from 1 to n) can be defined recursively. Let's take an example first to show how. Let's say that I know what are all the inverse pairs for n=4 and for k=0,1,2,3,4,....

Let's write down a few of them (in the format (n, k)):

(4, 0) : [1,2,3,4] (only one possibility with 0 inverse pairs)

(4, 1) : [2,1,3,4], [1,3,2,4], [1,2,4,3] (three possibilities with 1 inverse pair)

(4, 2) : [2,3,1,4], [2,1,4,3], [3,1,2,4], [1,3,4,2], [1,4,2,3] (five possibilities with 2 inverse pairs)

(4, 3) : [3,2,1,4], [2,3,4,1], [2,4,1,3], [3,1,4,2], [1,4,3,2], [4,1,2,3] (six possibilities with 3 inverse pairs)

... and so on

First observation is that, the maximum value of k for which there could be non-zero inverse pairs is :

Maximum value of k possible = $\frac{n * (n - 1)}{2}$ ,

which is what we will obtain with the inverted array i.e. [n, n-1, n-2, ..., 1]. Verify that, change in position in any pair of numbers will result in lesser number of inverse pairs.

Now coming back to our problem with n=4. Let's say that I want to obtain the number of inverse pairs with (5, 0). One can obtain the inverse pairs with 5, is by putting in 5 in the inverse pairs arrays obtained with 4, at the appropriate positions. For example, if we put 5 at the end of the array in (4, 0), we obtain the results for (5, 0), i.e. [1,2,3,4,5]. If we put 5 in any other position in any other arrays, we cannot obtain inverse pairs for (5, 0).

Similarly to obtain the inverse pairs for (5, 1), we put 5 between 3 and 4 in the array for (4, 0) to obtain [1,2,3,5,4], i.e. one inverse pair. Note that, we can also obtain one inverse pairs, if we put 5 at the end of each array in (4, 1), since it already has one inverse pair and by adding 5 at the end we are not changing that.

Thus, the number of inverse pairs with (5, 1) = number of inverse pairs for (4, 0) + number of inverse pairs for (4, 1).

If we go on increasing the value of k with n=5, we can observe a recursive formation :

N(5, k) = N(4, k) + N(4, k - 1) + .... + N(4, k - m)

Why did we stop at N(4, k - m) instead of going to N(4, 0) ? Observe that for k >= 5, we cannot obtain k inverse pairs with [1,2,3,4] by putting in 5 at any place in the array. Maximum, we obtain k=4 if we put 5 at the beginning. Similarly for k >= 6, we cannot obtain k inverse pairs with any array from (4, 1) by putting in 5 at any place.

Thus m = k if k < n, else m = n - 1.

Thus we have obtained the number of k inverse pairs for (n, k) using the memoized values of (n-1, k-p), where p ranges from 0 to m as seen in the above formula. Now let's write the code in python :

import collections

class Solution(object):
    def kInversePairs(self, n, k):
        cache = collections.defaultdict(dict)
        modulo = 10**9 + 7

        for m in range(1, n + 1):
            u = int(m * (m - 1) / 2)
            for q in range(k + 1):
                if q == 0:
                    cache[m][q] = 1

                elif q > u:
                    cache[m][q] = 0

                else:
                    sums = 0
                    t = q if q < m else m - 1

                    for p in range(t + 1):
                        sums += cache[m - 1][q - p] % modulo

                    cache[m][q] = sums % modulo

        return cache[n][k]

I am using the observation that whenever k = 0, the number of inverse pairs is 1, irrespective of the value of n.

Let's analyze the run time of the above code. It is of the $O(n * k * p)$ , now given that $p = O(n)$ , we have the total complexity to be $O(n^2 * k)$ for the above code. But the worst case run-time would be $O(n^4)$ , because as we earlier saw that $k = O(n^2)$ .

Can we do better ? The answer is yes.

Observe that, when we are computing N(n, k - 1), we are looping over from N(n - 1, k - 1) to N(n - 1, k - m - 1). Now in the next iteration when we want to compute N(n, k), we will loop over from N(n - 1, k) to N(n - 1, k - m). Now we see that we are doing redundant computation, because we have already computed the sum from N(n - 1, k - 1) to N(n - 1, k - m) in the previous iteration. Now we can memoize the computations further :

N(n, k) = N(n, k - 1) + N(n - 1, k) - N(n - 1, k - m - 1) if k - m - 1 >= 0 else N(n, k - 1) + N(n - 1, k)

Because N(n, k - 1) ends at N(n - 1, k - m - 1) but N(n, k) ends at N(n - 1, k - m), so we need to remove the extra term N(n - 1, k - m - 1) only if it was present.

import collections

class Solution(object):
    def kInversePairs(self, n, k):
        cache = collections.defaultdict(dict)
        modulo = 10**9 + 7

        for m in range(1, n + 1):
            u = int(m * (m - 1) / 2)
            for q in range(k + 1):
                if q == 0:
                    cache[m][q] = 1

                elif q > u:
                    cache[m][q] = 0

                else:
                    p = q if q < m else m - 1

                    if q - p - 1 >= 0:
                        cache[m][q] = (cache[m][q - 1] + cache[m - 1][q] - cache[m - 1][q - p - 1]) % modulo
                    else:
                        cache[m][q] = (cache[m][q - 1] + cache[m - 1][q]) % modulo

        return cache[n][k]

Now the run time of the above code is $O(n * k)$ . The worst case run-time is $O(n^3)$ given that $k = O(n^2)$ .