Problem Description

The K Inverse Pairs Array problem asks: Given two integers, n and k, return the number of different arrays consisting of numbers from 1 to n that have exactly k inverse pairs. An inverse pair is defined as a pair of indices (i, j) such that i < j and nums[i] > nums[j].

• Each array must be a permutation of the integers from 1 to n (no repeats, all numbers used exactly once).
• The answer may be large, so return it modulo 10^9 + 7.
• Constraints: 1 <= n <= 1000, 0 <= k <= 1000.

Thought Process

At first glance, one might consider generating all possible permutations of n and counting those with exactly k inverse pairs. However, this brute-force approach is computationally infeasible for large n (since there are n! permutations).

Instead, we look for patterns and relationships. Notably, the problem is well-suited for dynamic programming because:

• The solution for a given n and k can be constructed from solutions to smaller subproblems (smaller n and/or k).
• We can represent the state as dp[n][k]: the number of arrays of length n with exactly k inverse pairs.

The key is to find a recurrence relation that allows us to build up the answer efficiently without enumerating all permutations.

Solution Approach

We use dynamic programming with the following ideas:

1. State Definition:
   • dp[n][k] = number of permutations of 1..n with exactly k inverse pairs.
2. Base Case:
   • dp[0][0] = 1 (empty array has zero inverse pairs)
   • For all k > 0, dp[0][k] = 0
3. Recurrence Relation:
   • When adding the n-th number to a permutation of n-1 numbers, placing it at position i (from 0 to n-1) creates i new inverse pairs.
   • Thus, dp[n][k] = dp[n-1][k] + dp[n-1][k-1] + ... + dp[n-1][k-(n-1)] (for k-i >= 0).
   • To optimize, we use prefix sums to avoid redundant summation in each step.
4. Optimization:
   • Use prefix sums to compute each dp[n][k] in O(1) time after preprocessing.
   • Iterate up to n and k, filling the DP table.
5. Modulo Operation:
   • Since the answer may be large, take each result modulo 10^9 + 7.

Example Walkthrough

Consider n = 3 and k = 1.
All permutations of [1,2,3] are:

• [1,2,3] → 0 inverse pairs
• [1,3,2] → 1 inverse pair (3,2)
• [2,1,3] → 1 inverse pair (2,1)
• [2,3,1] → 2 inverse pairs (2,1), (3,1)
• [3,1,2] → 2 inverse pairs (3,1), (3,2)
• [3,2,1] → 3 inverse pairs (3,2), (3,1), (2,1)

There are 2 permutations with exactly 1 inverse pair: [1,3,2] and [2,1,3].

Using our DP approach:

• For n = 2: [1,2] (0), [2,1] (1)
• For n = 3, k = 1:
  • Placing 3 at position 0: add 0 inverses → dp[2][1]
  • Placing 3 at position 1: add 1 inverse → dp[2][0]
  • Placing 3 at position 2: add 2 inverses → not possible for k=1
• So, dp[3][1] = dp[2][1] + dp[2][0] = 1 + 1 = 2

Time and Space Complexity

• Brute-force approach:
  • Time: O(n!) (generating all permutations)
  • Space: O(n) (to store a permutation)
• Dynamic Programming approach:
  • Time: O(n*k) (each dp[n][k] computed in O(1) using prefix sums)
  • Space: O(n*k) (storing the DP table)

The optimized DP approach is feasible for the input constraints (n, k <= 1000).

Summary

The K Inverse Pairs Array problem is a classic example of using dynamic programming to count permutations with a certain property. By defining the right state and leveraging prefix sums for optimization, we avoid brute-force enumeration and achieve an efficient solution. The main insight is recognizing how placing the next largest number in various positions affects the inverse pair count, allowing us to build up the answer step by step.

Code Implementation

MOD = 10**9 + 7

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        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):
                left = j - min(j, i-1)
                dp[i][j] = (prefix[j+1] - prefix[left]) % MOD
        return dp[n][k]
      

class Solution {
public:
    int kInversePairs(int n, int k) {
        const int MOD = 1e9 + 7;
        vector<vector<int>> dp(n+1, vector<int>(k+1, 0));
        dp[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            vector<int> prefix(k+2, 0);
            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 left = j - min(j, i-1);
                dp[i][j] = (prefix[j+1] - prefix[left] + MOD) % MOD;
            }
        }
        return dp[n][k];
    }
};
      

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 left = j - Math.min(j, i-1);
                dp[i][j] = (prefix[j+1] - prefix[left] + MOD) % MOD;
            }
        }
        return dp[n][k];
    }
}
      

var kInversePairs = function(n, k) {
    const MOD = 1e9 + 7;
    let dp = Array.from({length: n+1}, () => Array(k+1).fill(0));
    dp[0][0] = 1;
    for (let i = 1; i <= n; ++i) {
        let 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) {
            let left = j - Math.min(j, i-1);
            dp[i][j] = (prefix[j+1] - prefix[left] + MOD) % MOD;
        }
    }
    return dp[n][k];
};