Leetcode 629. K Inverse Pairs Array

Problem Explanation:

This problem is asking to generate a kind of permutation from the numbers 1 to n with exactly k inverse pairs. An "inverse pair" is defined by the existence of a pair of elements, such that for i'th and j'th element in the array, if i < j and a[i] > a[j] this pair is considered as an inverse pair.

The key to solving this problem is dynamic programming.

To solve this problem, we can maintain a 2-D dp, where dp[i][j] means the number of permutations of 1 through i so that we achieve 'j' inverse pairs. To gain an intuition into why we use such a dp, consider that we need to permute numbers from 1 through n. We can fix one of these numbers at the end of our permutation and now we need to permute numbers from 1 through n-1 to achieve 'j' inverse pairs. But if our nth number is at the end of the permutation it can contribute to 0, 1, ..., n-1 inverse pairs. Hence, if j-n+1 is greater than 0, we should subtract the permutations which contribute to these many inverse pairs. This forms the crux of our recurrence relation.

Please note that this problem requires to return the answer module 10^9 + 7 as the answer might be very large.

Let's take n=3, K=1 as an example:

If we have 3 numbers and we want to have exactly 1 inverse pair, there are the following two permutations that satisfy the requirement: [1,3,2] and [2,1,3]. Hence, the output is 2.

Python Solution:

1
2python
3class Solution:
4    def kInversePairs(self, n: int, k: int) -> int:
5        MOD = 10**9 + 7
6        dp = [[0 for _ in range(k+1)] for _ in range(n+1)]
7        
8        for i in range(n+1):
9            dp[i][0] = 1
10            
11        for i in range(1, n+1):
12            for j in range(1, k+1):
13                dp[i][j] = (dp[i][j-1]+dp[i-1][j]) % MOD
14                if j-i>=0:
15                    dp[i][j] = (dp[i][j]-dp[i-1][j-i]+MOD) %MOD
16        return dp[n][k]

Python solution uses dynamic programming approach to find the count of permutations having exactly k inverse pairs. The dp array is initialized with all zeroes. The loop starts iterating from 1 to n+1 and for every i, dp[i][0] is set to 1 since there exists only one way to form a sequence with 0 inverse pairs (i.e., the sequence of numbers from 1 to n in increasing order). Then, it starts another nested loop inside the first loop from 1 to k+1 for each i and updates the dp table based on above mentioned logic. In the end, dp[n][k] is returned, where n is the given number and k is the given inverse pairs.

In this problem, the time complexity is O(nk) and the space complexity is O(nk) as the entire 2D dp array is used. JavaScript Solution:

The idea and approach for the JavaScript solution remains the same as Python, we use a 2-D array for dynamic programming and maintain our count of permutations. Here, we need to make sure to use BigInt for necessary calculations to ensure accuracy as large integer handling in JavaScript requires BigInt.

1
2javascript
3var kInversePairs = function(n, k) {
4    const MOD = BigInt(10**9 + 7);
5    const dp = Array.from({length:n+1}, () => Array(k+1).fill(BigInt(0)));
6    
7    for (let i = 0; i <= n; i++) {
8        dp[i][0] = BigInt(1)
9    }
10    
11    for (let i = 1; i <= n; i++) {
12        for (let j = 1; j <= k; j++) {
13            dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % MOD;
14            if (j-i >= 0) {
15                dp[i][j] = (dp[i][j] - dp[i-1][j-i] + MOD) %MOD;
16            }
17        }
18    }
19    return Number(dp[n][k])
20};

In the JavaScript solution, BigInt is used to handle relatively large numbers. The nested loop starts iterating from 1 to n+1 and k+1 for each n and k respectively, updates the dp table based on the calculated permutations and eventually returns dp[n][k].

Java Solution:

We can also solve this problem in Java. Like other solutions, we use a dynamic programming approach to solve this problem.

1
2java
3class Solution {
4    public int kInversePairs(int n, int k) {
5        int MOD = 1000000007;
6        int[][] dp = new int[n+1][k+1];
7        
8        for (int i = 0; i <= n; i++) {
9            dp[i][0] = 1;
10        }
11        
12        for (int i = 1; i <= n; i++) {
13            for (int j = 1; j <= k; j++) {
14                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % MOD;
15                if (j - i >= 0) {
16                    dp[i][j] = (dp[i][j] - dp[i - 1][j - i] + MOD) % MOD;
17                }
18            }
19        }
20        return dp[n][k];
21    }
22}

This Java solution works similar to the Python and JavaScript solutions. We keep calculating and storing our intermediate results in the dp array. These intermediate results are used to calculate the further permutations count. Finally, we return dp[n][k]. The time and space complexity of this solution is O(nk), same as above solutions.