K Inverse Pairs Array Problem

Problem

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 consist of numbers from 1 to n such that there are exactly k inverse pairs. Since the answer can be huge, return it modulo 10^9 + 7.

Examples

Example 1:

1
2
3
4
5

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:

1
2
3
4
5

Input:
n = 3, k = 1
Output:
 2
Explanation: The array [1,3,2] and [2,1,3] have exactly 1 inverse pair.

Solution

Method 1 – Dynamic Programming with Prefix Sums

Intuition

We can build up the answer for n and k by considering how many ways we can insert the largest number at different positions, which creates a certain number of new inverse pairs. Using prefix sums allows us to efficiently compute the DP transitions.

Approach

  1. Let dp[i][j] be the number of arrays of length i with exactly j inverse pairs.
  2. For each i from 1 to n, and each j from 0 to k, sum over all possible positions to insert the new number, using prefix sums to optimize.
  3. Return dp[n][k].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int kInversePairs(int n, int k) {
        int mod = 1e9+7;
        vector<vector<int>> dp(n+1, vector<int>(k+1));
        dp[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            vector<int> prefix(k+2);
            for (int j = 0; j <= k; ++j) prefix[j+1] = (prefix[j] + dp[i-1][j]) % mod;
            for (int j = 0; j <= k; ++j) {
                int l = max(0, j-i+1);
                dp[i][j] = (prefix[j+1] - prefix[l] + mod) % mod;
            }
        }
        return dp[n][k];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func kInversePairs(n int, k int) int {
    mod := int(1e9+7)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, k+1)
    }
    dp[0][0] = 1
    for i := 1; i <= n; i++ {
        prefix := make([]int, k+2)
        for j := 0; j <= k; j++ {
            prefix[j+1] = (prefix[j] + dp[i-1][j]) % mod
        }
        for j := 0; j <= k; j++ {
            l := j - i + 1
            if l < 0 { l = 0 }
            dp[i][j] = (prefix[j+1] - prefix[l] + mod) % mod
        }
    }
    return dp[n][k]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int kInversePairs(int n, int k) {
        int mod = 1000000007;
        int[][] dp = new int[n+1][k+1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            int[] prefix = new int[k+2];
            for (int j = 0; j <= k; ++j) prefix[j+1] = (prefix[j] + dp[i-1][j]) % mod;
            for (int j = 0; j <= k; ++j) {
                int l = Math.max(0, j-i+1);
                dp[i][j] = (prefix[j+1] - prefix[l] + mod) % mod;
            }
        }
        return dp[n][k];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun kInversePairs(n: Int, k: Int): Int {
        val mod = 1_000_000_007
        val dp = Array(n+1) { IntArray(k+1) }
        dp[0][0] = 1
        for (i in 1..n) {
            val prefix = IntArray(k+2)
            for (j in 0..k) prefix[j+1] = (prefix[j] + dp[i-1][j]) % mod
            for (j in 0..k) {
                val l = maxOf(0, j-i+1)
                dp[i][j] = (prefix[j+1] - prefix[l] + mod) % mod
            }
        }
        return dp[n][k]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        mod = 10**9+7
        dp = [[0]*(k+1) for _ in range(n+1)]
        dp[0][0] = 1
        for i in range(1, n+1):
            prefix = [0]*(k+2)
            for j in range(k+1):
                prefix[j+1] = (prefix[j] + dp[i-1][j]) % mod
            for j in range(k+1):
                l = max(0, j-i+1)
                dp[i][j] = (prefix[j+1] - prefix[l] + mod) % mod
        return dp[n][k]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn k_inverse_pairs(n: i32, k: i32) -> i32 {
        let n = n as usize;
        let k = k as usize;
        let modn = 1_000_000_007;
        let mut dp = vec![vec![0; k+1]; n+1];
        dp[0][0] = 1;
        for i in 1..=n {
            let mut prefix = vec![0; k+2];
            for j in 0..=k { prefix[j+1] = (prefix[j] + dp[i-1][j]) % modn; }
            for j in 0..=k {
                let l = if j+1 < i { 0 } else { j+1-i };
                dp[i][j] = (prefix[j+1] - prefix[l] + modn) % modn;
            }
        }
        dp[n][k]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    kInversePairs(n: number, k: number): number {
        const mod = 1e9+7;
        const dp = Array.from({length: n+1}, () => Array(k+1).fill(0));
        dp[0][0] = 1;
        for (let i = 1; i <= n; i++) {
            const prefix = Array(k+2).fill(0);
            for (let j = 0; j <= k; j++) prefix[j+1] = (prefix[j] + dp[i-1][j]) % mod;
            for (let j = 0; j <= k; j++) {
                const l = Math.max(0, j-i+1);
                dp[i][j] = (prefix[j+1] - prefix[l] + mod) % mod;
            }
        }
        return dp[n][k];
    }
}

Complexity

  • ⏰ Time complexity: O(n*k) where n is the array length and k is the number of inverse pairs. Each DP state is computed in constant time using prefix sums.
  • 🧺 Space complexity: O(n*k) for the DP table.