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 = ,
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 , now given that
, we have the total complexity to be
for the above code. But the worst case run-time would be
, because as we earlier saw that
.
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 . The worst case run-time is
given that
.
Categories: PROGRAMMING
Tags: Dynamic Programming, Inverse Pairs, Leetcode, Memoization