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 i_th and j_th 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 10⁹ + 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:

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];
}

629 - K Inverse Pairs Array

629. K Inverse Pairs Array (Hard)

Solution 1.

Solution 2. DP

Solution 3. DP + Cumulative Sum

All Problems

All Solutions

Welcome to Subscribe On Youtube

629. K Inverse Pairs Array (Hard)

Solution 1.

Solution 2. DP

Solution 3. DP + Cumulative Sum

All Problems

All Solutions