Here, We see K Inverse Pairs Array LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
K Inverse Pairs Array LeetCode Solution
Table of Contents
Problem Statement
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 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.
K Inverse Pairs Array LeetCode Solution C++
class Solution {
public:
int kInversePairs(int n, int k) {
int dp[1001][1001] = {1};
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
for (int x = 0; x <= min(j, i - 1); x++) {
if (j - x >= 0) {
dp[i][j] = (dp[i][j] + dp[i - 1][j - x]) % 1000000007;
}
}
}
}
return dp[n][k];
}
};
Code language: PHP (php)
K Inverse Pairs Array LeetCode Solution Java
class Solution {
public int kInversePairs(int n, int k) {
int[][] dp = new int[1001][1001];
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
for (int x = 0; x <= Math.min(j, i - 1); x++) {
if (j - x >= 0) {
dp[i][j] = (dp[i][j] + dp[i - 1][j - x]) % 1000000007;
}
}
}
}
return dp[n][k];
}
}
Code language: JavaScript (javascript)
K Inverse Pairs Array Solution JavaScript
var kInversePairs = function(n, k) {
const M = 1000000007;
let dp = new Array(1001).fill(0).map(() => new Array(1001).fill(0));
dp[0][0] = 1;
for (let i = 1; i <= n; i++) {
for (let j = 0; j <= k; j++) {
for (let x = 0; x <= Math.min(j, i - 1); x++) {
if (j - x >= 0) {
dp[i][j] = (dp[i][j] + dp[i - 1][j - x]) % M;
}
}
}
}
return dp[n][k];
};
Code language: JavaScript (javascript)
K Inverse Pairs Array Solution Python
class Solution(object):
def kInversePairs(self, n, k):
dp = [[0] * 1001 for _ in range(1001)]
dp[0][0] = 1
for i in range(1, n + 1):
for j in range(0, k + 1):
for x in range(0, min(j, i - 1) + 1):
if j - x >= 0:
dp[i][j] = (dp[i][j] + dp[i - 1][j - x]) % 1000000007
return dp[n][k]