LeetCode 3193: Count the Number of Inversions Solution

Master LeetCode problem 3193 (Count the Number of Inversions), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

3193. Count the Number of Inversions

Hard

Array Dynamic Programming

Problem Explanation

Explanation:

To solve this problem, we can use dynamic programming. We will iterate through the requirements and build a 2D array dp to keep track of the number of permutations with specific inversion counts up to each endi. We will then use this array to compute the total number of permutations that satisfy all requirements.

Initialize a 2D array dp of size (n+1) x (max_inversions+1) where max_inversions is the maximum inversion count in the requirements.
Initialize dp[0][0] = 1 as there is only one way to have 0 inversions with an empty prefix.
Iterate through the requirements and update dp accordingly.
Finally, multiply the values in the last row of dp to get the total number of permutations that satisfy all requirements.

Time Complexity: O(n * max_inversions)
Space Complexity: O(n * max_inversions)

Solution Code

class Solution {
    public int numberOfPermutations(int n, int[][] requirements) {
        int mod = 1000000007;
        int maxInversions = Arrays.stream(requirements).mapToInt(a -> a[1]).max().orElse(0);

        int[][] dp = new int[n + 1][maxInversions + 1];
        dp[0][0] = 1;

        for (int[] req : requirements) {
            int end = req[0], inversions = req[1];
            int[][] temp = new int[n + 1][maxInversions + 1];
            for (int i = 1; i <= n; i++) {
                for (int j = 0; j <= maxInversions; j++) {
                    temp[i][j] = dp[i][j];
                    if (i > end) {
                        temp[i][j] = (temp[i][j] + dp[i - 1][j - (i - 1 > end ? i - 1 - end : 0)]) % mod;
                    }
                }
            }
            dp = temp;
        }

        int result = 0;
        for (int i = 0; i <= maxInversions; i++) {
            result = (result + dp[n][i]) % mod;
        }

        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 3193 (Count the Number of Inversions)?

This page provides optimized solutions for LeetCode problem 3193 (Count the Number of Inversions) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3193 (Count the Number of Inversions)?

The time complexity for LeetCode 3193 (Count the Number of Inversions) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3193 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3193 in Java, C++, or Python.

Back to LeetCode Solutions