Sponsored
Sponsored
We use a two-dimensional dynamic programming array, where dp[i][j] represents the number of permutations of array {1, 2, ..., i} with exactly j inverse pairs. The transition is based on the idea that when we insert a new element into an existing permutation, it can create new inverse pairs from 0 up to i-1.
Time Complexity: O(n*k)
Space Complexity: O(n*k)
1function kInversePairs(n, k) {
2 const MOD = 1000000007;
3 const dp = Array.from({ length: n + 1 }, () => Array(k + 1).fill(0));
4 for (let i = 0; i <= n; i++) {
5 dp[i][0] = 1;
6 for (let j = 1; j <= k; j++) {
7 if (i > 0) {
8 dp[i][j] = (dp[i-1][j] + MOD - (j >= i ? dp[i-1][j-i] : 0)) % MOD;
9 }
10 dp[i][j] = (dp[i][j] + dp[i][j-1]) % MOD;
11 }
12 }
13 return (dp[n][k] + MOD - (k > 0 ? dp[n][k-1] : 0)) % MOD;
14}
15
16const n = 3, k = 1;
17console.log(kInversePairs(n, k));In JavaScript, arrays are dynamically used to form the DP table. The algorithm applies the formula iteratively to populate results for inverse pair counts, ensuring efficient memory use and adhering to operation constraints with modulo handling.