Algorithm

Problem Name: 629. K Inverse Pairs Array

Problem Link: https://leetcode.com/problems/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

x
–
+
cmd
n = 3, k = 0

Output

x
–
+
cmd
1

#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

x
–
+
cmd
n = 3, k = 0

Output

x
–
+
cmd
1

#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

x
–
+
cmd
n = 3, k = 1

Output

x
–
+
cmd
2

Demonstration

Previous
#628 Leetcode Maximum Product of Three Numbers Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#630 Leetcode Course Schedule III Solution in C, C++, Java, JavaScript, Python, C# Leetcode