Algorithm
Problem Name: 629. K Inverse Pairs Array
For an integer array nums
, an inverse pair is a pair of integers [i, j]
where 0 <= i < j < nums.length
and nums[i] > nums[j]
.
Given two integers n and k, return the number of different arrays consist of numbers from 1
to n
such that there are exactly k
inverse pairs. Since the answer can be huge, return it modulo 109 + 7
.
Example 1:
Input: n = 3, k = 0 Output: 1 Explanation: Only the array [1,2,3] which consists of numbers from 1 to 3 has exactly 0 inverse pairs.
Example 2:
Input: n = 3, k = 1 Output: 2 Explanation: The array [1,3,2] and [2,1,3] have exactly 1 inverse pair.
Constraints:
1 <= n <= 1000
0 <= k <= 1000
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int kInversePairs(int n, int k) {
int[][] dp = new int[n + 1][k + 1];
int mod = 1000000007;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
if (j == 0) {
dp[i][j] = 1;
} else {
int curr = (dp[i - 1][j] + mod - ((j - i) >= 0 ? dp[i - 1][j - i] : 0)) % mod;
dp[i][j] = (dp[i][j - 1] + curr) % mod;
}
}
}
return ((dp[n][k] + mod - (k > 0 ? dp[n][k - 1] : 0)) % mod);
}
}
Copy The Code &
Try With Live Editor
Input
Output
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const kInversePairs = function(n, k) {
const dp = Array.from({ length: n + 1 }, () => new Array(k + 1).fill(0))
for (let i = 1; i < n + 1; i++) {
dp[i][0] = 1
}
const MOD = 1e9 + 7
for (let i = 1; i < n + 1; i++) {
for (let j = 1; j < k + 1; j++) {
let val = (dp[i - 1][j] - (j >= i ? dp[i - 1][j - i] : 0) + MOD) % MOD
dp[i][j] = (dp[i][j - 1] + val) % MOD
}
}
return (dp[n][k] - (dp[n][k - 1] || 0) + MOD) % MOD
}
Copy The Code &
Try With Live Editor
Input
Output
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def kInversePairs(self, n, k):
dp = [1] + [0] * k
for i in range(2, n + 1):
for j in range(1, k + 1): dp[j] += dp[j - 1]
for j in range(k, 0, -1): dp[j] -= j - i >= 0 and dp[j - i]
return dp[-1] % (10 ** 9 + 7)
Copy The Code &
Try With Live Editor
Input
Output