Last updated on October 9th, 2024 at 06:13 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

K Inverse Pairs Array LeetCode Solution

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]