Last updated on January 18th, 2025 at 09:50 pm
Here, we see a K Inverse Pairs Array LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Level of Question
Hard
K Inverse Pairs Array LeetCode Solution
Table of Contents
1. 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.
2. Coding Pattern Used in Solution
The coding pattern used in this code is Dynamic Programming (DP). Specifically, it is a 2D DP table-based approach to solve the problem of counting the number of ways to form k inverse pairs in an array of size n.
3. Code Implementation in Different Languages
3.1 K Inverse Pairs Array 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];
}
};
3.2 K Inverse Pairs Array 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];
}
}
3.3 K Inverse Pairs Array 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];
};
3.4 K Inverse Pairs Array 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]
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n * k²) | O(n * k) |
| Java | O(n * k²) | O(n * k) |
| JavaScript | O(n * k²) | O(n * k) |
| Python | O(n * k²) | O(n * k) |
- The time complexity is dominated by the triple nested loops, where the innermost loop iterates up to
min(j, i-1). - The space complexity is determined by the size of the DP table, which is proportional to
n * k. - The modulo operation (
% 1000000007) ensures that the result does not overflow, but it does not affect the asymptotic complexity.