629. K Inverse Pairs Array LeetCode Solution

In this guide, you will get 629. K Inverse Pairs Array LeetCode Solution with the best time and space complexity. The solution to K Inverse Pairs Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
K Inverse Pairs Array solution in C++
K Inverse Pairs Array solution in Java
K Inverse Pairs Array solution in Python
Additional Resources

629. K Inverse Pairs Array LeetCode Solution image

Problem Statement of K Inverse Pairs Array

For an integer array nums, an inverse pair is a pair of integers [i, j] where 0 <= i < j nums[j].
Given two integers n and k, return the number of different arrays consisting 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

Complexity Analysis

Time Complexity: O(nk)
Space Complexity: O(nk)

629. K Inverse Pairs Array LeetCode Solution in C++

class Solution {
 public:
  int kInversePairs(int n, int k) {
    constexpr int kMod = 1'000'000'007;
    // dp[i][j] := the number of permutations of numbers 1..i with j inverse
    // pairs
    vector<vector<int>> dp(n + 1, vector<int>(k + 1));

    // If there's no inverse pair, the permutation is unique "123..i".
    for (int i = 0; i <= n; ++i)
      dp[i][0] = 1;

    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= k; ++j) {
        dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % kMod;
        if (j - i >= 0)
          dp[i][j] = (dp[i][j] - dp[i - 1][j - i] + kMod) % kMod;
      }

    return dp[n][k];
  }
};
/* code provided by PROGIEZ */

629. K Inverse Pairs Array LeetCode Solution in Java

class Solution {
  public int kInversePairs(int n, int k) {
    final int kMod = 1_000_000_007;
    // dp[i][j] := the number of permutations of numbers 1..i with j inverse pairs
    int[][] dp = new int[n + 1][k + 1];

    // If there's no inverse pair, the permutation is unique "123..i".
    for (int i = 0; i <= n; ++i)
      dp[i][0] = 1;

    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= k; ++j) {
        dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % kMod;
        if (j - i >= 0)
          dp[i][j] = (dp[i][j] - dp[i - 1][j - i] + kMod) % kMod;
      }

    return dp[n][k];
  }
}
// code provided by PROGIEZ

629. K Inverse Pairs Array LeetCode Solution in Python

class Solution:
  def kInversePairs(self, n: int, k: int) -> int:
    kMod = 1_000_000_007
    # dp[i][j] := the number of permutations of numbers 1..i with j inverse pairs
    dp = [[0] * (k + 1) for _ in range(n + 1)]

    # If there's no inverse pair, the permutation is unique '123..i'
    for i in range(n + 1):
      dp[i][0] = 1

    for i in range(1, n + 1):
      for j in range(1, k + 1):
        dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % kMod
        if j - i >= 0:
          dp[i][j] = (dp[i][j] - dp[i - 1][j - i] + kMod) % kMod

    return dp[n][k]
 # code by PROGIEZ