##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/629.html

# 629. K Inverse Pairs Array (Hard)

Given two integers n and k, find how many different arrays consist of numbers from 1 to n such that there are exactly k inverse pairs.

We define an inverse pair as following: For ith and jth element in the array, if i < j and a[i] > a[j] then it's an inverse pair; Otherwise, it's not.

Since the answer may be very large, the answer should be 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 pair.


Example 2:

Input: n = 3, k = 1
Output: 2
Explanation:
The array [1,3,2] and [2,1,3] have exactly 1 inverse pair.


Note:

1. The integer n is in the range [1, 1000] and k is in the range [0, 1000].

Companies:
Works Applications

Related Topics:
Dynamic Programming

## Solution 1.

Denote R(n, k) as the result number, P as a permutation.

For n = 1, only 1 case for k = 0. So R(1, 0) = 1.

| 1 |               // If P[0] = 1


For n = 2:

| 1 |               // If P[0] = 1
| 1 |           // If P[0] = 2
|
V
| 1 | 1 |


For n = 3:

| 1 | 1 |               // If P[0] = 1
| 1 | 1 |           // If P[0] = 2
| 1 | 1 |       // If P[0] = 3
|
V
| 1 | 2 | 2 | 1 |



For n = 4:

| 1 | 2 | 2 | 1 |              // If P[0] = 1
| 1 | 2 | 2 | 1 |          // If P[0] = 2
| 1 | 2 | 2 | 1 |      // If P[0] = 3
| 1 | 2 | 2 | 1 |  // If P[0] = 4
|
V
| 1 | 3 | 5 | 6 | 5 | 3 | 1 |


// OJ: https://leetcode.com/problems/k-inverse-pairs-array/
// Time: O(N * K^2)
// Space: O(K)
class Solution {
public:
int kInversePairs(int n, int k) {
if (k > n * (n - 1) / 2) return 0;
int mod = 1e9 + 7;
vector<int> prev(1, 1);
for (int i = 1; i <= n; ++i) {
vector<int> cnt(min(k + 1, (int)prev.size() + i - 1));
for (int j = 0; j < i; ++j) {
for (int t = 0; t < prev.size(); ++t) {
if (j + t > k) break;
cnt[j + t] = (cnt[j + t] + prev[t]) % mod;
}
}
prev = cnt;
}
return prev[k];
}
};


## Solution 2. DP

Denote F(N, K) as the result.

Observations:

• Valid range of K is [0, N * (N - 1) / 2]. F(N, K) = 0 if K[0, N * (N - 1) / 2].
• F(N, 0) = F(N, N * (N - 1) / 2) = 1.

For F(N, K), let’s pick 1, 2, …, N as the first number:

• When 1 is picked, we need to compute F(N - 1, K).
• When 2 is picked, we need to compute F(N - 1, K - 1).
• When N is picked, we need to compute F(N - 1, K - (N - 1)).

Eventually F(N, K) = Sum(F(N - 1, K) + F(N - 1, K - 1) + ... + F(N - 1, K - (N - 1)).

We can use this formula to compute F(n, K) for N = 1, 2, 3, ..., N.

// OJ: https://leetcode.com/problems/k-inverse-pairs-array/
// Time: O(NK * min(N, K))
// Space: O(K)
class Solution {
public:
int kInversePairs(int N, int K) {
if (K > N * (N - 1) / 2) return 0;
vector<int> m(K + 1, 0);
m[0] = 1;
int mod = 1e9 + 7;
for (int n = 2; n <= N; ++n) {
for (int k = min(K, (n * (n - 1) / 2)); k > 0; --k) {
for (int i = max(0, k - n + 1); i < k && m[i]; ++i) {
m[k] = (m[k] + m[i]) % mod;
}
}
}
return m[K];
}
};


## Solution 3. DP + Cumulative Sum

In Solution 2, we alway compute the sum of a segment of the previous row. Considering this, we can use Cumulative Sum to make it faster.

Denote G(N, K) as Sum{k=[0,K]}(F(N, k)).

G(N, K) = G(N, K - 1) + F(N, K)
= G(N, K - 1) + [F(N - 1, K - min(K, N - 1)) + ... + F(N - 1, K)]
= G(N, K - 1) + [G(N - 1, K) - G(N - 1, K - min(K, N - 1) - 1)]


After all the G(N, K) are computed, we can get F(N, K) = G(N, K) - G(N, K - 1).

// OJ: https://leetcode.com/problems/k-inverse-pairs-array/
// Time: O(NK)
// Space: O(K)
class Solution {
public:
int kInversePairs(int N, int K) {
if (K > N * (N - 1) / 2) return 0;
vector<vector<int>> dp(2, vector<int>(K + 1, 0));
dp[0][0] = dp[1][0] = 1;
int mod = 1e9 + 7;
for (int n = 2; n <= N; ++n) {
int bound = min(K, n * (n - 1) / 2);
for (int k = 1; k <= bound; ++k) {
dp[n % 2][k] = (dp[n % 2][k - 1] + (mod + dp[(n - 1) % 2][k] - dp[(n - 1) % 2][k - min(k, n - 1) - 1]) % mod) % mod;
}
}
return dp[N % 2][K];
}
};

• class Solution {
public int kInversePairs(int n, int k) {
final int MODULO = 1000000007;
int[][] dp = new int[n + 1][k + 1];
for (int i = 1; i <= n; i++)
dp[i][0] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= k; j++) {
int sum = (dp[i - 1][j] + dp[i][j - 1]) % MODULO;
dp[i][j] = (sum - ((j - i < 0) ? 0 : dp[i - 1][j - i]) + MODULO) % MODULO;
}
}
return dp[n][k];
}
}

############

class Solution {
public int kInversePairs(int n, int k) {
final int mod = (int) 1e9 + 7;
int[] f = new int[k + 1];
int[] s = new int[k + 2];
f[0] = 1;
Arrays.fill(s, 1);
s[0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= k; ++j) {
f[j] = (s[j + 1] - s[Math.max(0, j - (i - 1))] + mod) % mod;
}
for (int j = 1; j <= k + 1; ++j) {
s[j] = (s[j - 1] + f[j - 1]) % mod;
}
}
return f[k];
}
}

• // OJ: https://leetcode.com/problems/k-inverse-pairs-array/
// Time: O(N * K^2)
// Space: O(K)
class Solution {
public:
int kInversePairs(int n, int k) {
if (k > n * (n - 1) / 2) return 0;
int mod = 1e9 + 7;
vector<int> prev(1, 1);
for (int i = 1; i <= n; ++i) {
vector<int> cnt(min(k + 1, (int)prev.size() + i - 1));
for (int j = 0; j < i; ++j) {
for (int t = 0; t < prev.size(); ++t) {
if (j + t > k) break;
cnt[j + t] = (cnt[j + t] + prev[t]) % mod;
}
}
prev = cnt;
}
return prev[k];
}
};

• class Solution:
def kInversePairs(self, n: int, k: int) -> int:
mod = 1000000007
dp, pre = [0] * (k + 1), [0] * (k + 2)
for i in range(1, n + 1):
dp[0] = 1

# dp[i][j] = dp[i - 1][j - (i - 1)] + ... + dp[i - 1][j]
for j in range(1, k + 1):
dp[j] = (pre[j + 1] - pre[max(0, j - i + 1)] + mod) % mod

for j in range(1, k + 2):
pre[j] = (pre[j - 1] + dp[j - 1]) % mod

return dp[k]

############

class Solution(object):
def kInversePairs(self, n, k):
"""
:type n: int
:type k: int
:rtype: int
"""
MOD = 10 ** 9 + 7
upper = n * (n - 1) / 2
if k == 0 or k == upper:
return 1
if k > upper:
return 0
dp = [0] * (k + 1)
dp[0] = 1
for i in range(1, n + 1):
temp = [1] + [0] * k
for j in range(k + 1):
temp[j] = (temp[j - 1] + dp[j]) % MOD
if j - i >= 0:
temp[j] = (temp[j] - dp[j - i]) % MOD
dp = temp
return dp[k]


• func kInversePairs(n int, k int) int {
f := make([]int, k+1)
s := make([]int, k+2)
f[0] = 1
for i, x := range f {
s[i+1] = s[i] + x
}
const mod = 1e9 + 7
for i := 1; i <= n; i++ {
for j := 1; j <= k; j++ {
f[j] = (s[j+1] - s[max(0, j-(i-1))] + mod) % mod
}
for j := 1; j <= k+1; j++ {
s[j] = (s[j-1] + f[j-1]) % mod
}
}
return f[k]
}

func max(a, b int) int {
if a > b {
return a
}
return b
}


• function kInversePairs(n: number, k: number): number {
const f: number[] = new Array(k + 1).fill(0);
f[0] = 1;
const s: number[] = new Array(k + 2).fill(1);
s[0] = 0;
const mod: number = 1e9 + 7;
for (let i = 1; i <= n; ++i) {
for (let j = 1; j <= k; ++j) {
f[j] = (s[j + 1] - s[Math.max(0, j - (i - 1))] + mod) % mod;
}
for (let j = 1; j <= k + 1; ++j) {
s[j] = (s[j - 1] + f[j - 1]) % mod;
}
}
return f[k];
}