3193. Count the Number of Inversions

Description

You are given an integer n and a 2D array requirements, where requirements[i] = [end_i, cnt_i] represents the end index and the inversion count of each requirement.

A pair of indices (i, j) from an integer array nums is called an inversion if:

i < j and nums[i] > nums[j]

Return the number of permutations perm of [0, 1, 2, ..., n - 1] such that for all requirements[i], perm[0..end_i] has exactly cnt_i inversions.

Since the answer may be very large, return it modulo 10⁹ + 7.

Example 1:

Input: n = 3, requirements = [[2,2],[0,0]]

Output: 2

Explanation:

The two permutations are:

[2, 0, 1]
- Prefix [2, 0, 1] has inversions (0, 1) and (0, 2).
- Prefix [2] has 0 inversions.
[1, 2, 0]
- Prefix [1, 2, 0] has inversions (0, 2) and (1, 2).
- Prefix [1] has 0 inversions.

Example 2:

Input: n = 3, requirements = [[2,2],[1,1],[0,0]]

Output: 1

Explanation:

The only satisfying permutation is [2, 0, 1]:

Prefix [2, 0, 1] has inversions (0, 1) and (0, 2).
Prefix [2, 0] has an inversion (0, 1).
Prefix [2] has 0 inversions.

Example 3:

Input: n = 2, requirements = [[0,0],[1,0]]

Output: 1

Explanation:

The only satisfying permutation is [0, 1]:

Prefix [0] has 0 inversions.
Prefix [0, 1] has no inversions.

Constraints:

2 <= n <= 300
1 <= requirements.length <= n
requirements[i] = [end_i, cnt_i]
0 <= end_i <= n - 1
0 <= cnt_i <= 400
The input is generated such that there is at least one i such that end_i == n - 1.
The input is generated such that all end_i are unique.

Solutions

Solution 1: Dynamic Programming

Thinking

Count permutations whose prefix inversion counts match given constraints. Placing value \(i\) may add \(0..i\) inversions, so DP tracks how many numbers are placed and how many inversions they hold.

A constraint pins one prefix; other layers still enumerate \(j\). With \(m\le 400\) the triple loop passes.

Let \(f[i][j]\) be the ways to fill \([0..i]\) with \(j\) inversions. A required prefix fills only that column; otherwise add \(f[i-1][j-k]\) for \(k\le\min(i,j)\). The first prefix must have zero inversions.

We define \(f[i][j]\) as the number of permutations of \([0..i]\) with \(j\) inversions. Consider the relationship between the number \(a_i\) at index \(i\) and the previous \(i\) numbers. If \(a_i\) is smaller than \(k\) of the previous numbers, then each of these \(k\) numbers forms an inversion pair with \(a_i\), contributing to \(k\) inversions. Therefore, we can derive the state transition equation:

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

Since the problem requires the number of inversions in \([0..\textit{end}_i]\) to be \(\textit{cnt}_i\), when we calculate for \(i = \textit{end}_i\), we only need to compute \(f[i][\textit{cnt}_i]\). The rest of \(f[i][..]\) will be \(0\).

The time complexity is \(O(n \times m \times \min(n, m))\), and the space complexity is \(O(n \times m)\). Here, \(m\) is the maximum number of inversions, and in this problem, \(m \le 400\).

Python3JavaC++GoTypeScript

class Solution:
    def numberOfPermutations(self, n: int, requirements: List[List[int]]) -> int:
        req = [-1] * n
        for end, cnt in requirements:
            req[end] = cnt
        if req[0] > 0:
            return 0
        req[0] = 0
        mod = 10**9 + 7
        m = max(req)
        f = [[0] * (m + 1) for _ in range(n)]
        f[0][0] = 1
        for i in range(1, n):
            l, r = 0, m
            if req[i] >= 0:
                l = r = req[i]
            for j in range(l, r + 1):
                for k in range(min(i, j) + 1):
                    f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod
        return f[n - 1][req[n - 1]]

class Solution {
    public int numberOfPermutations(int n, int[][] requirements) {
        int[] req = new int[n];
        Arrays.fill(req, -1);
        int m = 0;
        for (var r : requirements) {
            req[r[0]] = r[1];
            m = Math.max(m, r[1]);
        }
        if (req[0] > 0) {
            return 0;
        }
        req[0] = 0;
        final int mod = (int) 1e9 + 7;
        int[][] f = new int[n][m + 1];
        f[0][0] = 1;
        for (int i = 1; i < n; ++i) {
            int l = 0, r = m;
            if (req[i] >= 0) {
                l = r = req[i];
            }
            for (int j = l; j <= r; ++j) {
                for (int k = 0; k <= Math.min(i, j); ++k) {
                    f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod;
                }
            }
        }
        return f[n - 1][req[n - 1]];
    }
}

class Solution {
public:
    int numberOfPermutations(int n, vector<vector<int>>& requirements) {
        vector<int> req(n, -1);
        int m = 0;
        for (const auto& r : requirements) {
            req[r[0]] = r[1];
            m = max(m, r[1]);
        }
        if (req[0] > 0) {
            return 0;
        }
        req[0] = 0;
        const int mod = 1e9 + 7;
        vector<vector<int>> f(n, vector<int>(m + 1, 0));
        f[0][0] = 1;
        for (int i = 1; i < n; ++i) {
            int l = 0, r = m;
            if (req[i] >= 0) {
                l = r = req[i];
            }
            for (int j = l; j <= r; ++j) {
                for (int k = 0; k <= min(i, j); ++k) {
                    f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod;
                }
            }
        }
        return f[n - 1][req[n - 1]];
    }
};

func numberOfPermutations(n int, requirements [][]int) int {
    req := make([]int, n)
    for i := range req {
        req[i] = -1
    }
    for _, r := range requirements {
        req[r[0]] = r[1]
    }
    if req[0] > 0 {
        return 0
    }
    req[0] = 0
    m := slices.Max(req)
    const mod = int(1e9 + 7)
    f := make([][]int, n)
    for i := range f {
        f[i] = make([]int, m+1)
    }
    f[0][0] = 1
    for i := 1; i < n; i++ {
        l, r := 0, m
        if req[i] >= 0 {
            l, r = req[i], req[i]
        }
        for j := l; j <= r; j++ {
            for k := 0; k <= min(i, j); k++ {
                f[i][j] = (f[i][j] + f[i-1][j-k]) % mod
            }
        }
    }
    return f[n-1][req[n-1]]
}

function numberOfPermutations(n: number, requirements: number[][]): number {
    const req: number[] = Array(n).fill(-1);
    for (const [end, cnt] of requirements) {
        req[end] = cnt;
    }
    if (req[0] > 0) {
        return 0;
    }
    req[0] = 0;
    const m = Math.max(...req);
    const mod = 1e9 + 7;
    const f = Array.from({ length: n }, () => Array(m + 1).fill(0));
    f[0][0] = 1;
    for (let i = 1; i < n; ++i) {
        let [l, r] = [0, m];
        if (req[i] >= 0) {
            l = r = req[i];
        }
        for (let j = l; j <= r; ++j) {
            for (let k = 0; k <= Math.min(i, j); ++k) {
                f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod;
            }
        }
    }
    return f[n - 1][req[n - 1]];
}

3193. Count the Number of Inversions

Description

Solutions

Solution 1: Dynamic Programming

Comments