3193. Count the Number of Inversions

Description

You are given an integer n and a 2D array requirements, where requirements[i] = [endi, cnti] 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..endi] has exactly cnti inversions.

Since the answer may be very large, return it modulo 109 + 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 an inversion (0, 1).

 

Constraints:

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

Solutions

Solution 1: Dynamic Programming

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]];
}

Comments