Problem

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 10^9 + 7.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

1
2
3
4
5
6
7

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

1
2
3
4
5
6

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.

Solution

Method 1 – Dynamic Programming with Prefix Constraints

Intuition

We want to count the number of permutations of [0, 1, ..., n-1] such that for each prefix ending at endi, the number of inversions is exactly cnti. This is a classic DP on permutations with inversion count, but with additional prefix constraints.

Approach

  1. Let dp[i][k] be the number of ways to arrange the first i numbers with exactly k inversions.
  2. For each prefix length i, if there is a requirement for that prefix, only keep the DP for the required inversion count.
  3. For each i from 1 to n, update dp[i][k] by adding all possible ways to insert the new number at position j (which adds j new inversions).
  4. Use prefix sums to optimize the DP transitions.
  5. The answer is the sum of all valid DP states for the full array that satisfy all requirements.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
    int countInversions(int n, vector<vector<int>>& requirements) {
        const int MOD = 1e9+7;
        vector<int> req(n, -1);
        for (auto& r : requirements) req[r[0]] = r[1];
        vector<vector<int>> dp(n+1, vector<int>(n*(n-1)/2+1));
        dp[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            vector<int> pre(n*(n-1)/2+2);
            for (int k = 0; k <= (i-1)*(i-2)/2; ++k) pre[k+1] = (pre[k] + dp[i-1][k]) % MOD;
            for (int k = 0; k <= i*(i-1)/2; ++k) {
                int l = max(0, k-(i-1)), r = min(k, (i-1)*(i-2)/2);
                if (l > r) continue;
                dp[i][k] = (pre[r+1] - pre[l] + MOD) % MOD;
            }
            if (req[i-1] != -1) {
                vector<int> ndp(n*(n-1)/2+1);
                ndp[req[i-1]] = dp[i][req[i-1]];
                dp[i] = ndp;
            }
        }
        int ans = 0;
        for (int k = 0; k <= n*(n-1)/2; ++k) ans = (ans + dp[n][k]) % MOD;
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
    def countInversions(self, n: int, requirements: list[list[int]]) -> int:
        MOD = 10**9+7
        req = [-1]*n
        for endi, cnti in requirements:
            req[endi] = cnti
        max_inv = n*(n-1)//2
        dp = [0]*(max_inv+1)
        dp[0] = 1
        for i in range(1, n+1):
            ndp = [0]*(max_inv+1)
            pre = [0]*(max_inv+2)
            for k in range((i-1)*(i-2)//2+1):
                pre[k+1] = (pre[k] + dp[k]) % MOD
            for k in range(i*(i-1)//2+1):
                l = max(0, k-(i-1))
                r = min(k, (i-1)*(i-2)//2)
                if l > r: continue
                ndp[k] = (pre[r+1] - pre[l]) % MOD
            if req[i-1] != -1:
                tmp = [0]*(max_inv+1)
                tmp[req[i-1]] = ndp[req[i-1]]
                ndp = tmp
            dp = ndp
        return sum(dp) % MOD
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    public int countInversions(int n, int[][] requirements) {
        int MOD = 1_000_000_007;
        int[] req = new int[n];
        Arrays.fill(req, -1);
        for (int[] r : requirements) req[r[0]] = r[1];
        int maxInv = n*(n-1)/2;
        int[] dp = new int[maxInv+1];
        dp[0] = 1;
        for (int i = 1; i <= n; ++i) {
            int[] ndp = new int[maxInv+1];
            int[] pre = new int[maxInv+2];
            for (int k = 0; k <= (i-1)*(i-2)/2; ++k) pre[k+1] = (pre[k] + dp[k]) % MOD;
            for (int k = 0; k <= i*(i-1)/2; ++k) {
                int l = Math.max(0, k-(i-1)), r = Math.min(k, (i-1)*(i-2)/2);
                if (l > r) continue;
                ndp[k] = (pre[r+1] - pre[l] + MOD) % MOD;
            }
            if (req[i-1] != -1) {
                int[] tmp = new int[maxInv+1];
                tmp[req[i-1]] = ndp[req[i-1]];
                ndp = tmp;
            }
            dp = ndp;
        }
        int ans = 0;
        for (int v : dp) ans = (ans + v) % MOD;
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    fun countInversions(n: Int, requirements: Array<IntArray>): Int {
        val MOD = 1_000_000_007
        val req = IntArray(n) { -1 }
        for ((endi, cnti) in requirements) req[endi] = cnti
        val maxInv = n*(n-1)/2
        var dp = IntArray(maxInv+1)
        dp[0] = 1
        for (i in 1..n) {
            val ndp = IntArray(maxInv+1)
            val pre = IntArray(maxInv+2)
            for (k in 0..(i-1)*(i-2)/2) pre[k+1] = (pre[k] + dp[k]) % MOD
            for (k in 0..i*(i-1)/2) {
                val l = maxOf(0, k-(i-1))
                val r = minOf(k, (i-1)*(i-2)/2)
                if (l > r) continue
                ndp[k] = (pre[r+1] - pre[l] + MOD) % MOD
            }
            if (req[i-1] != -1) {
                val tmp = IntArray(maxInv+1)
                tmp[req[i-1]] = ndp[req[i-1]]
                for (j in 0..maxInv) ndp[j] = tmp[j]
            }
            dp = ndp
        }
        return dp.sum() % MOD
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

impl Solution {
    pub fn count_inversions(n: i32, requirements: Vec<Vec<i32>>) -> i32 {
        const MOD: i32 = 1_000_000_007;
        let n = n as usize;
        let mut req = vec![-1; n];
        for r in requirements.iter() {
            req[r[0] as usize] = r[1];
        }
        let max_inv = n*(n-1)/2;
        let mut dp = vec![0; max_inv+1];
        dp[0] = 1;
        for i in 1..=n {
            let mut ndp = vec![0; max_inv+1];
            let mut pre = vec![0; max_inv+2];
            for k in 0..=(i-1)*(i-2)/2 {
                pre[k+1] = (pre[k] + dp[k]) % MOD;
            }
            for k in 0..=i*(i-1)/2 {
                let l = k.saturating_sub(i-1);
                let r = k.min((i-1)*(i-2)/2);
                if l > r { continue; }
                ndp[k] = (pre[r+1] - pre[l] + MOD) % MOD;
            }
            if req[i-1] != -1 {
                let mut tmp = vec![0; max_inv+1];
                tmp[req[i-1] as usize] = ndp[req[i-1] as usize];
                ndp = tmp;
            }
            dp = ndp;
        }
        dp.iter().fold(0, |acc, &v| (acc + v) % MOD)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    countInversions(n: number, requirements: number[][]): number {
        const MOD = 1_000_000_007;
        const req = Array(n).fill(-1);
        for (const [endi, cnti] of requirements) req[endi] = cnti;
        const maxInv = n*(n-1)/2;
        let dp = Array(maxInv+1).fill(0);
        dp[0] = 1;
        for (let i = 1; i <= n; ++i) {
            const ndp = Array(maxInv+1).fill(0);
            const pre = Array(maxInv+2).fill(0);
            for (let k = 0; k <= (i-1)*(i-2)/2; ++k) pre[k+1] = (pre[k] + dp[k]) % MOD;
            for (let k = 0; k <= i*(i-1)/2; ++k) {
                const l = Math.max(0, k-(i-1)), r = Math.min(k, (i-1)*(i-2)/2);
                if (l > r) continue;
                ndp[k] = (pre[r+1] - pre[l] + MOD) % MOD;
            }
            if (req[i-1] !== -1) {
                const tmp = Array(maxInv+1).fill(0);
                tmp[req[i-1]] = ndp[req[i-1]];
                for (let j = 0; j <= maxInv; ++j) ndp[j] = tmp[j];
            }
            dp = ndp;
        }
        return dp.reduce((a, b) => (a + b) % MOD, 0);
    }
}

Complexity

  • ⏰ Time complexity: O(n^2) due to DP and prefix sum optimizations.
  • 🧺 Space complexity: O(n^2) for DP arrays.