# Count the Number of Inversions
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-the-number-of-inversions)
Canonical: https://scaleengineer.com/dsa/problems/count-the-number-of-inversions
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## 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** `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.

# Approaches
## Brute-Force by Generating All Permutations
The most straightforward, yet inefficient, approach is to generate every possible permutation of the numbers `[0, 1, ..., n-1]`. For each permutation, we then verify if it meets all the conditions specified in the `requirements` array. We maintain a count of the permutations that satisfy all conditions.
**Time:** O(n! * L * n^2), where `L` is the number of requirements. Generating `n!` permutations is the bottleneck. For each permutation, we check `L` requirements, and each check takes up to `O(n^2)` time to count inversions. This is computationally prohibitive. · **Space:** O(n) to store a single permutation.
**Pros:** Simple to understand and implement the logic.; Guaranteed to find the correct answer if it runs to completion.
**Cons:** Extremely high time complexity, making it infeasible for the given constraints (`n` up to 300).; The number of permutations `n!` grows astonishingly fast, exceeding time limits for `n` greater than about 10 or 11.
### Explanation
This method involves a brute-force search over the entire solution space of permutations.

We can implement a function that generates permutations one by one. For each generated permutation, we have a helper function that validates it against the `requirements`. The validation function iterates through each requirement, computes the inversion count for the corresponding prefix of the permutation, and compares it with the required count. If all requirements are met, we count this permutation as a valid one.

Here is a conceptual code snippet for this approach:
```java
class Solution {
    // This approach is too slow and will time out.
    public int numberOfPermutations(int n, int[][] requirements) {
        int[] p = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = i;
        }
        long count = 0;
        long mod = 1_000_000_007;
        
        // This do-while loop iterates through all n! permutations.
        do {
            if (check(p, requirements)) {
                count++;
            }
        } while (nextPermutation(p));
        
        return (int) (count % mod);
    }

    private boolean check(int[] p, int[][] requirements) {
        for (int[] req : requirements) {
            int end = req[0];
            int expectedCnt = req[1];
            if (countInversions(p, end) != expectedCnt) {
                return false;
            }
        }
        return true;
    }

    private int countInversions(int[] p, int end) {
        int inversions = 0;
        for (int i = 0; i <= end; i++) {
            for (int j = i + 1; j <= end; j++) {
                if (p[i] > p[j]) {
                    inversions++;
                }
            }
        }
        return inversions;
    }
    
    // A standard implementation of nextPermutation would be needed here.
    private boolean nextPermutation(int[] p) {
        // ... implementation details ...
        return true; // if next permutation exists
    }
}
```
### Algorithm
1. Create a function to generate all permutations of `[0, 1, ..., n-1]`. A common way is to use an algorithm like Heap's algorithm or by repeatedly finding the next lexicographical permutation.
2. Initialize a counter for valid permutations to zero.
3. Loop through each of the `n!` permutations.
4. For each permutation, check if it satisfies all given `requirements`.
5. To check a permutation, iterate through each requirement `[end_i, cnt_i]`.
6. For a given requirement, calculate the number of inversions in the prefix of the permutation of length `end_i + 1`.
7. An inversion is a pair of indices `(j, k)` such that `j < k` and `perm[j] > perm[k]`.
8. If the calculated number of inversions does not match `cnt_i` for any requirement, the permutation is invalid. Stop checking this permutation and move to the next one.
9. If the permutation satisfies all requirements, increment the counter.
10. After checking all `n!` permutations, the value of the counter is the answer.

## Dynamic Programming with Prefix Sums
This problem can be solved efficiently using dynamic programming. The core idea is to build the permutations incrementally by length, from 1 to `n`. At each step `i`, we calculate the number of permutations of length `i` for each possible number of inversions `j`. The key is the recurrence relation that connects the number of permutations of length `i` with `j` inversions to the counts for permutations of length `i-1`.
**Time:** O(n * max_cnt). The main loop runs `n` times. Inside the loop, calculating prefix sums and the new DP table each take `O(max_cnt)` time. Given `n <= 300` and `max_cnt <= 400`, this is very efficient. · **Space:** O(n + max_cnt), where `max_cnt` is the maximum inversion count in `requirements`. We use a map for requirements (`O(n)`) and DP/prefix sum arrays of size `O(max_cnt)`.
**Pros:** Highly efficient and passes within the time limits for the given constraints.; Systematically builds the solution by solving smaller, overlapping subproblems.; The use of prefix sums optimizes the DP transition from O(i) to O(1) for each state.
**Cons:** The logic is more complex than a brute-force approach.; Requires understanding of dynamic programming and the specific recurrence for counting inversions in permutations.
### Explanation
Let `dp[i][j]` be the number of permutations of `[0, 1, ..., i-1]` with exactly `j` inversions. A permutation of length `i` is formed by taking a permutation of `[0, ..., i-2]` and inserting the number `i-1`. Since `i-1` is the largest number, inserting it at the `k`-th position from the end adds `k` new inversions (`0 <= k < i`). This leads to the recurrence: `dp[i][j] = sum_{k=0}^{i-1} dp[i-1][j-k]`. This sum can be optimized using prefix sums.

We can use a 1D DP array and iterate from length 1 to `n`, updating the counts at each step. After each step `i`, we apply the constraint from `requirements` for prefixes of length `i`, if any, by zeroing out counts for non-matching inversion numbers.

```java
import java.util.Map;
import java.util.HashMap;

class Solution {
    public int numberOfPermutations(int n, int[][] requirements) {
        int MOD = 1_000_000_007;
        Map<Integer, Integer> reqMap = new HashMap<>();
        int maxCnt = 0;
        for (int[] req : requirements) {
            // Use length (end_i + 1) as key
            reqMap.put(req[0] + 1, req[1]);
            maxCnt = Math.max(maxCnt, req[1]);
        }

        // dp[j] will store the number of permutations of length `i` with `j` inversions.
        long[] dp = new long[maxCnt + 1];
        dp[0] = 1; // Base case: 1 permutation of length 0 ([]) with 0 inversions.

        for (int i = 1; i <= n; i++) {
            long[] newDp = new long[maxCnt + 1];
            long[] prefixSum = new long[maxCnt + 1];
            
            // Calculate prefix sums for the previous DP table (length i-1)
            prefixSum[0] = dp[0];
            for (int j = 1; j <= maxCnt; j++) {
                prefixSum[j] = (prefixSum[j - 1] + dp[j]) % MOD;
            }

            // Calculate new DP table for length i
            for (int j = 0; j <= maxCnt; j++) {
                // Sum of dp[j-k] for k from 0 to i-1
                long ways = prefixSum[j];
                if (j >= i) {
                    ways = (ways - prefixSum[j - i] + MOD) % MOD;
                }
                newDp[j] = ways;
            }
            
            dp = newDp;

            // Apply requirement for the current length i
            if (reqMap.containsKey(i)) {
                int requiredCnt = reqMap.get(i);
                if (requiredCnt > maxCnt) { // Impossible requirement
                    return 0;
                }
                for (int j = 0; j <= maxCnt; j++) {
                    if (j != requiredCnt) {
                        dp[j] = 0;
                    }
                }
            }
        }

        // The problem guarantees a requirement for end = n-1 (length n).
        return (int) dp[reqMap.get(n)];
    }
}
```
### Algorithm
1. Pre-process the `requirements` array into a map for efficient lookups, mapping `end_i + 1` (prefix length) to `cnt_i`.
2. Determine the maximum required inversion count, `max_cnt`, from the requirements. This will be the size of our DP array.
3. Initialize a DP array, `dp`, of size `max_cnt + 1`. `dp[j]` will store the number of valid permutations of the current length with `j` inversions. Start with `dp[0] = 1` representing one empty permutation with 0 inversions.
4. Iterate `i` from 1 to `n`. In each iteration `i`, we calculate the DP table for permutations of length `i` based on the table for length `i-1`.
5. Inside the loop, first compute a prefix sum array `ps` for the current `dp` array. `ps[j] = (ps[j-1] + dp[j]) % MOD`.
6. Create a `new_dp` array. For each `j` from 0 to `max_cnt`, calculate `new_dp[j]` using the recurrence `dp[i][j] = sum_{k=0}^{i-1} dp[i-1][j-k]`. This sum is efficiently found using the prefix sum array: `ps[j] - ps[j-i]` (with modulo arithmetic).
7. After computing `new_dp`, update `dp = new_dp`.
8. Check if there is a requirement for length `i`. If `reqMap` contains `i`, let the required count be `c`. Enforce the constraint by setting `dp[j] = 0` for all `j != c`.
9. After the loop finishes (i.e., `i=n`), the answer is the value in `dp` at the index corresponding to the final requirement's count, `dp[reqMap.get(n)]`.

# Solutions
### Java

```java
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)1 e9 + 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]];
  }
}

```

### CPP

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

```

### Python

```python
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]]

```