Count the Number of Inversions

Hard

#2836Time: 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)`.

Patterns

Dynamic Programming

Data structures

Array

Prompt

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 an inversion (0, 1).

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.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Algorithm

Pre-process the requirements array into a map for efficient lookups, mapping end_i + 1 (prefix length) to cnt_i.
Determine the maximum required inversion count, max_cnt, from the requirements. This will be the size of our DP array.
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.
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.
Inside the loop, first compute a prefix sum array ps for the current dp array. ps[j] = (ps[j-1] + dp[j]) % MOD.
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).
After computing new_dp, update dp = new_dp.
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.
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)].

Walkthrough

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.

1import java.util.Map;2import java.util.HashMap;3 4class Solution {5    public int numberOfPermutations(int n, int[][] requirements) {6        int MOD = 1_000_000_007;7        Map<Integer, Integer> reqMap = new HashMap<>();8        int maxCnt = 0;9        for (int[] req : requirements) {10            // Use length (end_i + 1) as key11            reqMap.put(req[0] + 1, req[1]);12            maxCnt = Math.max(maxCnt, req[1]);13        }14 15        // dp[j] will store the number of permutations of length `i` with `j` inversions.16        long[] dp = new long[maxCnt + 1];17        dp[0] = 1; // Base case: 1 permutation of length 0 ([]) with 0 inversions.18 19        for (int i = 1; i <= n; i++) {20            long[] newDp = new long[maxCnt + 1];21            long[] prefixSum = new long[maxCnt + 1];22            23            // Calculate prefix sums for the previous DP table (length i-1)24            prefixSum[0] = dp[0];25            for (int j = 1; j <= maxCnt; j++) {26                prefixSum[j] = (prefixSum[j - 1] + dp[j]) % MOD;27            }28 29            // Calculate new DP table for length i30            for (int j = 0; j <= maxCnt; j++) {31                // Sum of dp[j-k] for k from 0 to i-132                long ways = prefixSum[j];33                if (j >= i) {34                    ways = (ways - prefixSum[j - i] + MOD) % MOD;35                }36                newDp[j] = ways;37            }38            39            dp = newDp;40 41            // Apply requirement for the current length i42            if (reqMap.containsKey(i)) {43                int requiredCnt = reqMap.get(i);44                if (requiredCnt > maxCnt) { // Impossible requirement45                    return 0;46                }47                for (int j = 0; j <= maxCnt; j++) {48                    if (j != requiredCnt) {49                        dp[j] = 0;50                    }51                }52            }53        }54 55        // The problem guarantees a requirement for end = n-1 (length n).56        return (int) dp[reqMap.get(n)];57    }58}

Complexity

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)`.

Trade-offs

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.

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.

Algorithm

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.
Initialize a counter for valid permutations to zero.
Loop through each of the n! permutations.
For each permutation, check if it satisfies all given requirements.
To check a permutation, iterate through each requirement [end_i, cnt_i].
For a given requirement, calculate the number of inversions in the prefix of the permutation of length end_i + 1.
An inversion is a pair of indices (j, k) such that j < k and perm[j] > perm[k].
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.
If the permutation satisfies all requirements, increment the counter.
After checking all n! permutations, the value of the counter is the answer.

Walkthrough

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:

1class Solution {2    // This approach is too slow and will time out.3    public int numberOfPermutations(int n, int[][] requirements) {4        int[] p = new int[n];5        for (int i = 0; i < n; i++) {6            p[i] = i;7        }8        long count = 0;9        long mod = 1_000_000_007;10        11        // This do-while loop iterates through all n! permutations.12        do {13            if (check(p, requirements)) {14                count++;15            }16        } while (nextPermutation(p));17        18        return (int) (count % mod);19    }20 21    private boolean check(int[] p, int[][] requirements) {22        for (int[] req : requirements) {23            int end = req[0];24            int expectedCnt = req[1];25            if (countInversions(p, end) != expectedCnt) {26                return false;27            }28        }29        return true;30    }31 32    private int countInversions(int[] p, int end) {33        int inversions = 0;34        for (int i = 0; i <= end; i++) {35            for (int j = i + 1; j <= end; j++) {36                if (p[i] > p[j]) {37                    inversions++;38                }39            }40        }41        return inversions;42    }43    44    // A standard implementation of nextPermutation would be needed here.45    private boolean nextPermutation(int[] p) {46        // ... implementation details ...47        return true; // if next permutation exists48    }49}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int numberOfPermutations(int n, int[][] requirements) {4    int[] req = new int[n];5    Arrays.fill(req, -1);6    int m = 0;7    for (var r : requirements) {8      req[r[0]] = r[1];9      m = Math.max(m, r[1]);10    }11    if (req[0] > 0) {12      return 0;13    }14    req[0] = 0;15    final int mod = (int)1 e9 + 7;16    int[][] f = new int[n][m + 1];17    f[0][0] = 1;18    for (int i = 1; i < n; ++i) {19      int l = 0, r = m;20      if (req[i] >= 0) {21        l = r = req[i];22      }23      for (int j = l; j <= r; ++j) {24        for (int k = 0; k <= Math.min(i, j); ++k) {25          f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod;26        }27      }28    }29    return f[n - 1][req[n - 1]];30  }31}

1class Solution {2public:3  int numberOfPermutations(int n, vector<vector<int>> &requirements) {4    vector<int> req(n, -1);5    int m = 0;6    for (const auto &r : requirements) {7      req[r[0]] = r[1];8      m = max(m, r[1]);9    }10    if (req[0] > 0) {11      return 0;12    }13    req[0] = 0;14    const int mod = 1e9 + 7;15    vector<vector<int>> f(n, vector<int>(m + 1, 0));16    f[0][0] = 1;17    for (int i = 1; i < n; ++i) {18      int l = 0, r = m;19      if (req[i] >= 0) {20        l = r = req[i];21      }22      for (int j = l; j <= r; ++j) {23        for (int k = 0; k <= min(i, j); ++k) {24          f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod;25        }26      }27    }28    return f[n - 1][req[n - 1]];29  }30};

1class Solution:2    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]]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int numberOfPermutations(int n, int[][] requirements) {4    int[] req = new int[n];5    Arrays.fill(req, -1);6    int m = 0;7    for (var r : requirements) {8      req[r[0]] = r[1];9      m = Math.max(m, r[1]);10    }11    if (req[0] > 0) {12      return 0;13    }14    req[0] = 0;15    final int mod = (int)1 e9 + 7;16    int[][] f = new int[n][m + 1];17    f[0][0] = 1;18    for (int i = 1; i < n; ++i) {19      int l = 0, r = m;20      if (req[i] >= 0) {21        l = r = req[i];22      }23      for (int j = l; j <= r; ++j) {24        for (int k = 0; k <= Math.min(i, j); ++k) {25          f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod;26        }27      }28    }29    return f[n - 1][req[n - 1]];30  }31}

1class Solution {2public:3  int numberOfPermutations(int n, vector<vector<int>> &requirements) {4    vector<int> req(n, -1);5    int m = 0;6    for (const auto &r : requirements) {7      req[r[0]] = r[1];8      m = max(m, r[1]);9    }10    if (req[0] > 0) {11      return 0;12    }13    req[0] = 0;14    const int mod = 1e9 + 7;15    vector<vector<int>> f(n, vector<int>(m + 1, 0));16    f[0][0] = 1;17    for (int i = 1; i < n; ++i) {18      int l = 0, r = m;19      if (req[i] >= 0) {20        l = r = req[i];21      }22      for (int j = l; j <= r; ++j) {23        for (int k = 0; k <= min(i, j); ++k) {24          f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod;25        }26      }27    }28    return f[n - 1][req[n - 1]];29  }30};

1class Solution:2    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]]

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.