K Inverse Pairs Array - Leetcode Solution

The problem statement for K Inverse Pairs Array on LeetCode is as follows:

Given two integers n and k, you need to find the total number of different arrays that have exactly k inverse pairs. An inverse pair is defined as a pair of integers (i, j) where i < j and a[i] > a[j].

The solution to this problem is based on the concept of dynamic programming. We can consider the problem as a sub-problem of a larger problem, which is to find the number of permutations of length n. The total number of permutations of length n is n!.

We can represent the number of permutations of length n with k inverse pairs as F(n, k). The solution to the problem is F(n, k).

We can use the following recursion to compute F(n, k):

F(n, k) = F(n-1, k) + F(n-1, k-1) + F(n-1, k-2) + ... + F(n-1, k-n+1)

The above recursion can be explained as follows:

• If we fix the last element of the array to be n, then there will be no inverse pairs among the first n-1 elements. So, we need to find the number of permutations of length n-1 that have k inverse pairs. This gives us F(n-1, k).
• If we fix the last element of the array to be n-1, then there will be exactly 1 inverse pair that involves n-1. So, we need to find the number of permutations of length n-1 that have k-1 inverse pairs. This gives us F(n-1, k-1).
• If we fix the last element of the array to be n-2, then there will be exactly 2 inverse pairs that involve n-2. So, we need to find the number of permutations of length n-1 that have k-2 inverse pairs. This gives us F(n-1, k-2).
• Similarly, we can go on fixing the last element of the array to be n-i, where i varies from 1 to n-1, and compute the number of permutations of length n-1 that have k-i inverse pairs.

We can use memoization to avoid recomputing the same subproblems multiple times.

The base case for the recursion is:

F(0, 0) = 1

We have only one permutation of length 0, which has zero inverse pairs.

The final solution to the problem is F(n, k).

Here is the Python code that implements the above algorithm:

def kInversePairs(n: int, k: int) -> int: memo = [[-1 for _ in range(k+1)] for _ in range(n+1)] return kInversePairsHelper(n, k, memo)

def kInversePairsHelper(n: int, k: int, memo: List[List[int]]) -> int: if n == 0: return 1 if k < 0: return 0 if memo[n][k] != -1: return memo[n][k] total = 0 for i in range(n): total += kInversePairsHelper(n-1, k-i, memo) total %= 1000000007 memo[n][k] = total return total

We use a 2D memoization array to store the results of subproblems. The function kInversePairsHelper() is a recursive function that implements the above recursion with memoization. We return the result modulo 1000000007 to avoid overflow.

The time complexity of the above algorithm is O(n^2k), and the space complexity is O(nk), where n and k are the input parameters.

1