Welcome to Subscribe On Youtube

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..\text{end}_i]$ to be $\text{cnt}_i$, when we calculate for $i = \text{end}_i$, we only need to compute $f[i][\text{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$.

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

All Problems

All Solutions