629. K Inverse Pairs Array

Description

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 10⁹ + 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.

Constraints:

1 <= n <= 1000
0 <= k <= 1000

Solutions

Solution 1: Dynamic Programming + Prefix Sum

We define \(f[i][j]\) as the number of arrays of length \(i\) with \(j\) inverse pairs. Initially, \(f[0][0] = 1\), and the rest \(f[i][j] = 0\).

Next, we consider how to obtain \(f[i][j]\).

Assume the first \(i-1\) numbers are already determined, and now we need to insert the number \(i\). We discuss the cases of inserting \(i\) into each position:

If \(i\) is inserted into the 1st position, the number of inverse pairs increases by \(i-1\), so \(f[i][j] += f[i-1][j-(i-1)]\).
If \(i\) is inserted into the 2nd position, the number of inverse pairs increases by \(i-2\), so \(f[i][j] += f[i-1][j-(i-2)]\).
...
If \(i\) is inserted into the \((i-1)\)th position, the number of inverse pairs increases by 1, so \(f[i][j] += f[i-1][j-1]\).
If \(i\) is inserted into the \(i\)th position, the number of inverse pairs does not change, so \(f[i][j] += f[i-1][j]\).

Therefore, \(f[i][j] = \sum_{k=1}^{i} f[i-1][j-(i-k)]\).

We notice that the calculation of \(f[i][j]\) actually involves prefix sums, so we can use prefix sums to optimize the calculation process. Moreover, since \(f[i][j]\) only depends on \(f[i-1][j]\), we can use a one-dimensional array to optimize the space complexity.

The time complexity is \(O(n \times k)\), and the space complexity is \(O(k)\). Here, \(n\) and \(k\) are the array length and the number of inverse pairs, respectively.

Python3JavaC++GoTypeScript

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        mod = 10**9 + 7
        f = [1] + [0] * k
        s = [0] * (k + 2)
        for i in range(1, n + 1):
            for j in range(1, k + 1):
                f[j] = (s[j + 1] - s[max(0, j - (i - 1))]) % mod
            for j in range(1, k + 2):
                s[j] = (s[j - 1] + f[j - 1]) % mod
        return f[k]

class Solution {
    public int kInversePairs(int n, int k) {
        final int mod = (int) 1e9 + 7;
        int[] f = new int[k + 1];
        int[] s = new int[k + 2];
        f[0] = 1;
        Arrays.fill(s, 1);
        s[0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= k; ++j) {
                f[j] = (s[j + 1] - s[Math.max(0, j - (i - 1))] + mod) % mod;
            }
            for (int j = 1; j <= k + 1; ++j) {
                s[j] = (s[j - 1] + f[j - 1]) % mod;
            }
        }
        return f[k];
    }
}

class Solution {
public:
    int kInversePairs(int n, int k) {
        int f[k + 1];
        int s[k + 2];
        memset(f, 0, sizeof(f));
        f[0] = 1;
        fill(s, s + k + 2, 1);
        s[0] = 0;
        const int mod = 1e9 + 7;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= k; ++j) {
                f[j] = (s[j + 1] - s[max(0, j - (i - 1))] + mod) % mod;
            }
            for (int j = 1; j <= k + 1; ++j) {
                s[j] = (s[j - 1] + f[j - 1]) % mod;
            }
        }
        return f[k];
    }
};

func kInversePairs(n int, k int) int {
    f := make([]int, k+1)
    s := make([]int, k+2)
    f[0] = 1
    for i, x := range f {
        s[i+1] = s[i] + x
    }
    const mod = 1e9 + 7
    for i := 1; i <= n; i++ {
        for j := 1; j <= k; j++ {
            f[j] = (s[j+1] - s[max(0, j-(i-1))] + mod) % mod
        }
        for j := 1; j <= k+1; j++ {
            s[j] = (s[j-1] + f[j-1]) % mod
        }
    }
    return f[k]
}

function kInversePairs(n: number, k: number): number {
    const f: number[] = Array(k + 1).fill(0);
    f[0] = 1;
    const s: number[] = Array(k + 2).fill(1);
    s[0] = 0;
    const mod: number = 1e9 + 7;
    for (let i = 1; i <= n; ++i) {
        for (let j = 1; j <= k; ++j) {
            f[j] = (s[j + 1] - s[Math.max(0, j - (i - 1))] + mod) % mod;
        }
        for (let j = 1; j <= k + 1; ++j) {
            s[j] = (s[j - 1] + f[j - 1]) % mod;
        }
    }
    return f[k];
}

629. K Inverse Pairs Array

Description

Solutions

Solution 1: Dynamic Programming + Prefix Sum

Comments