Scale Engineer

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] = [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

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

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

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.

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

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.

Solutions

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

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 →

Next problem