Last updated on August 3rd, 2024 at 10:09 pm
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
Topics
Dynamic Programming
Level of Question
Hard
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.
1. 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]; } };
2. 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]; } }
3. 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]; };
4. 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]