3193. Count the Number of Inversions LeetCode Solution

In this guide, you will get 3193. Count the Number of Inversions LeetCode Solution with the best time and space complexity. The solution to Count the Number of Inversions problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Count the Number of Inversions solution in C++
Count the Number of Inversions solution in Java
Count the Number of Inversions solution in Python
Additional Resources

3193. Count the Number of Inversions LeetCode Solution image

Problem Statement of Count the Number of Inversions

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

Complexity Analysis

Time Complexity: O(400n^2) = O(n^2)
Space Complexity: O(400n) = O(n)

3193. Count the Number of Inversions LeetCode Solution in C++

class Solution {
 public:
  int numberOfPermutations(int n, vector<vector<int>>& requirements) {
    constexpr int kMod = 1'000'000'007;
    constexpr int kMaxInversions = 400;
    // dp[i][j] := the number of ways to arrange the first i numbers of the
    // permutation s.t. there are j inversions
    vector<vector<int>> dp(n + 1, vector<int>(kMaxInversions + 1));
    vector<int> endToCnt(n + 1, -1);

    for (const vector<int>& requirement : requirements) {
      const int end = requirement[0];
      const int cnt = requirement[1];
      endToCnt[end + 1] = cnt;
    }

    // There's only one way to arrange a single number with zero inversions.
    dp[1][0] = 1;

    for (int i = 2; i <= n; ++i)
      for (int newInversions = 0; newInversions < i; ++newInversions)
        for (int j = 0; j + newInversions <= kMaxInversions; ++j) {
          const int inversionsAfterInsertion = j + newInversions;
          if (endToCnt[i] != -1 && inversionsAfterInsertion != endToCnt[i])
            continue;
          dp[i][inversionsAfterInsertion] += dp[i - 1][j];
          dp[i][inversionsAfterInsertion] %= kMod;
        }

    return dp[n][endToCnt[n]];
  }
};
/* code provided by PROGIEZ */

3193. Count the Number of Inversions LeetCode Solution in Java

class Solution {
  public int numberOfPermutations(int n, int[][] requirements) {
    final int kMod = 1_000_000_007;
    final int kMaxInversions = 400;
    // dp[i][j] := the number of ways to arrange the first i numbers of the
    // permutation such that there are j inversions
    int[][] dp = new int[n + 1][kMaxInversions + 1];
    int[] endToCnt = new int[n + 1];
    Arrays.fill(endToCnt, -1);

    for (int[] requirement : requirements) {
      final int end = requirement[0];
      final int cnt = requirement[1];
      endToCnt[end + 1] = cnt;
    }

    // There's only one way to arrange a single number with zero inversions.
    dp[1][0] = 1;

    for (int i = 2; i <= n; ++i)
      for (int newInversions = 0; newInversions < i; ++newInversions)
        for (int j = 0; j + newInversions <= kMaxInversions; ++j) {
          final int inversionsAfterInsertion = j + newInversions;
          if (endToCnt[i] != -1 && inversionsAfterInsertion != endToCnt[i])
            continue;
          dp[i][inversionsAfterInsertion] += dp[i - 1][j];
          dp[i][inversionsAfterInsertion] %= kMod;
        }

    return dp[n][endToCnt[n]];
  }
}
// code provided by PROGIEZ

3193. Count the Number of Inversions LeetCode Solution in Python

class Solution:
  def numberOfPermutations(self, n: int, requirements: list[list[int]]) -> int:
    kMod = 1_000_000_007
    kMaxInversions = 400
    # dp[i][j] := the number of ways to arrange the first i numbers of the
    # permutation s.t. there are j inversions
    dp = [[0] * (kMaxInversions + 1) for _ in range(n + 1)]
    endToCnt = {end + 1: cnt for end, cnt in requirements}

    # There's only one way to arrange a single number with zero inversions.
    dp[1][0] = 1

    for i in range(2, n + 1):
      for newInversions in range(i):
        for j in range(kMaxInversions - newInversions + 1):
          inversionsAfterInsertion = j + newInversions
          if i in endToCnt and inversionsAfterInsertion != endToCnt[i]:
            continue
          dp[i][inversionsAfterInsertion] += dp[i - 1][j]
          dp[i][inversionsAfterInsertion] %= kMod

    return dp[n][endToCnt[n]]
 # code by PROGIEZ