Facebook Pixel

3193. Count the Number of Inversions

HardArrayDynamic Programming
Leetcode Link

Problem Description

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^9 + 7.

Intuition

To solve the problem of finding the number of permutations with exactly cnt_i inversions at index end_i, we can use a dynamic programming approach. The core idea is to systematically build permutations by considering the effect of each new element as it is added to the permutation.

Define f[i][j] as the number of permutations of the first i+1 numbers that result in exactly j inversions. We expand upon these notions to construct the state transitions:

  1. If we place a number a_i at position i, then it can form inversions with any of the previous elements in the permutation. Specifically, if number a_i is smaller than k of the previous numbers, those numbers will each form an inversion with a_i.

  2. Hence, for each j inversions, we consider k inversions contributed by a_i, leading to the transition relation:

    • f[i][j] = sum(f[i-1][j-k]) for k from 0 to min(i, j)

By iterating this process across all indices up to n and ensuring that at each specified end_i position the inversion count matches cnt_i, we can count the valid permutations.

Finally, using modular arithmetic helps manage potentially large answers by keeping calculations stable and efficient.

Learn more about Dynamic Programming patterns.

Solution Approach

To achieve the goal of finding the number of permutations with specified inversion constraints, we use a dynamic programming approach. The key idea is to build up solutions incrementally while keeping track of the number of inversions.

Dynamic Programming Table

We set up a 2D array f, where f[i][j] represents the number of permutations of the first i+1 elements with exactly j inversions.

Transition Relation

The transition between the states is based on the number of new inversions a newly added element can create. If a_i is placed and forms k inversions with previous elements, the transition is described by:

f[i][j] = sum(f[i-1][j-k]) for each k, where 0 <= k <= min(i, j)

Implementation Steps

  1. Initialization: Begin by initializing the table f with zeroes and place f[0][0] = 1 as the base case, indicating that there is exactly one permutation of the first element with zero inversions.

  2. Requirements Handling: Read the requirements and initialize an array req[] where req[end_i] = cnt_i, signifying the inversion constraint directly at end_i. If req[0] is set and greater than 0, the result is immediately 0, as a single element can't form inversions.

  3. Dynamic Programming Loop:

    • For each element position i from 1 to n-1:
      • Determine the inversion range l to r. If req[i] is specified, then l = r = req[i].
      • For each possible inversion count j from l to r:
        • Calculate the number of ways by summing previous states f[i-1][j-k].

  4. Result Extraction: The solution is given by f[n-1][req[n-1]], which gives the number of permutations of all n elements with the inversion count at the last requirement position as specified.

Complexity

This approach ensures efficient computation through careful indexing and counting, utilizing the properties of permutations and inversions. The use of modulo 10^9 + 7 guarantees that we manage large numbers within computational limits.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

To illustrate the approach, consider a small example with n = 3 and requirements = [[2, 1]]. This means we need to find permutations of [0, 1, 2] such that the subarray from the start up to index 2 has exactly one inversion.

  1. Initialization:

    • Create a DP table f where f[i][j] represents the number of permutations of the first i+1 numbers with exactly j inversions.
    • Initialize f[0][0] = 1 since there is exactly one way to order one element with zero inversions.

  2. Building the DP Table:

    • Process for i = 1 (considering a sequence of two elements, [0, 1]):
      • For j = 0, calculate f[1][0] = f[0][0] = 1. This means there is one way to arrange two numbers with zero inversions, which is [0, 1].
      • For j = 1, calculate f[1][1] = f[0][0] = 1. This represents one way to have one inversion, by arranging [1, 0].

  3. Extending to i = 2 (full permutation [0, 1, 2]):

    • For j = 0, calculate f[2][0] = f[1][0] = 1. Only [0, 1, 2] has zero inversions.
    • For j = 1, calculate f[2][1] = f[1][0] + f[1][1] = 1 + 1 = 2. These permutations are [0, 2, 1] and [1, 0, 2].
    • For j = 2, calculate using f[2][2] = f[1][1] = 1. The permutation [2, 0, 1] forms two inversions.

  4. Requirement Verification:

    • We're interested in f[2][1] since we need the subarray perm[0..2] to have exactly one inversion.
    • From f[2][1] = 2, we find there are two valid permutations that satisfy our condition: [0, 2, 1] and [1, 0, 2].

  5. Result:

    • Return the result modulo 10^9 + 7. Although unnecessary for small numbers, this is crucial for larger cases.
    • Final result: 2.

This walkthrough demonstrates use of dynamic programming to respect given inversion constraints, revealing valid permutations incrementally.

Solution Implementation

1from typing import List
2
3class Solution:
4    def numberOfPermutations(self, n: int, requirements: List[List[int]]) -> int:
5        # Initialize an array where each element represents a requirement for the ending index
6        req = [-1] * n
7        for end, cnt in requirements:
8            req[end] = cnt
9      
10        # If the first element has a requirement greater than 0, 
11        # then it's impossible to have such a permutation
12        if req[0] > 0:
13            return 0
14        req[0] = 0
15      
16        mod = 10**9 + 7  # Set a modulus for large numbers to prevent overflow
17      
18        # Find the maximum requirement
19        max_req = max(req)
20      
21        # Initialize a 2D list to store the number of ways permutations can meet requirements
22        dp = [[0] * (max_req + 1) for _ in range(n)]
23      
24        # Base case: The first element must meet the zero requirement, using one way
25        dp[0][0] = 1
26      
27        # Fill the dp table
28        for i in range(1, n):
29            # Determine the range of counts to consider for the current element
30            l, r = 0, max_req
31            if req[i] >= 0:
32                l = r = req[i]
33          
34            # Calculate the number of permutations for each requirement
35            for j in range(l, r + 1):
36                # Sum all possible previous states that could lead to the current state
37                for k in range(min(i, j) + 1):
38                    dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % mod
39      
40        # Return the result for the nth element with its requirement
41        return dp[n - 1][req[n - 1]]
42
1import java.util.Arrays;
2
3class Solution {
4    public int numberOfPermutations(int n, int[][] requirements) {
5        // Array to store required values for each position, initialized to -1
6        int[] req = new int[n];
7        Arrays.fill(req, -1);
8      
9        // Variable to store the maximum requirement value
10        int maxRequirement = 0;
11      
12        // Populate the req array and find the maximum requirement value
13        for (int[] r : requirements) {
14            req[r[0]] = r[1];
15            maxRequirement = Math.max(maxRequirement, r[1]);
16        }
17      
18        // If there is a requirement for the first position that is greater than 0, return 0
19        if (req[0] > 0) {
20            return 0;
21        }
22      
23        // Set the requirement for the first position to 0
24        req[0] = 0;
25      
26        // Define the modulus value for large numbers
27        final int MOD = (int) 1e9 + 7;
28      
29        // Create a 2D array to store the number of valid permutations
30        int[][] dp = new int[n][maxRequirement + 1];
31      
32        // Initialize the first position's requirement
33        dp[0][0] = 1;
34      
35        // Iterate through positions from 1 to n-1
36        for (int i = 1; i < n; ++i) {
37            int left = 0, right = maxRequirement;
38            // If a requirement is specified for the current position, set bounds to that requirement
39            if (req[i] >= 0) {
40                left = right = req[i];
41            }
42          
43            // Calculate number of permutations for each possible value of 'j'
44            for (int j = left; j <= right; ++j) {
45                // Add up valid permutations from previous position
46                for (int k = 0; k <= Math.min(i, j); ++k) {
47                    dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD;
48                }
49            }
50        }
51      
52        // Return the number of valid permutations for the final position's requirement
53        return dp[n - 1][req[n - 1]];
54    }
55}
56
1class Solution {
2public:
3    int numberOfPermutations(int n, vector<vector<int>>& requirements) {
4        // Vector to store the requirement for each position
5        vector<int> req(n, -1);
6        int maxReq = 0;
7
8        // Populate the requirements and find the maximum requirement value
9        for (const auto& r : requirements) {
10            req[r[0]] = r[1];
11            maxReq = max(maxReq, r[1]);
12        }
13
14        // If the first position has a requirement other than 0, return 0
15        if (req[0] > 0) {
16            return 0;
17        }
18
19        // Set the requirement for the first position to 0
20        req[0] = 0;
21      
22        // Define the modulo constant
23        const int mod = 1e9 + 7;
24      
25        // 2D vector to store permutations count based on position and requirement
26        vector<vector<int>> permCount(n, vector<int>(maxReq + 1, 0));
27      
28        // Initialize the first position with 1 permutation fulfilling the requirement
29        permCount[0][0] = 1;
30      
31        // Loop through each position
32        for (int i = 1; i < n; ++i) {
33            int left = 0, right = maxReq;
34          
35            // If a requirement is set for this position, restrict the range
36            if (req[i] >= 0) {
37                left = right = req[i];
38            }
39          
40            // Calculate permutations for each requirement value
41            for (int j = left; j <= right; ++j) {
42                // Sum the permutations using previous values according to Pascal's rule
43                for (int k = 0; k <= min(i, j); ++k) {
44                    permCount[i][j] = (permCount[i][j] + permCount[i - 1][j - k]) % mod;
45                }
46            }
47        }
48      
49        // Return the number of valid permutations for the last position's requirement
50        return permCount[n - 1][req[n - 1]];
51    }
52};
53
1// Function to calculate the number of permutations of size 'n' 
2// satisfying given requirements
3function numberOfPermutations(n: number, requirements: number[][]): number {
4    // Initialize an array with -1 to track specific permutation requirements at each index
5    const req: number[] = Array(n).fill(-1);
6
7    // Populate the 'req' array with given requirements
8    for (const [end, cnt] of requirements) {
9        req[end] = cnt;
10    }
11
12    // If the first position has a requirement greater than 0, it's impossible to meet, so return 0
13    if (req[0] > 0) {
14        return 0;
15    }
16
17    // Set the first position's requirement to 0, as it must start from there
18    req[0] = 0;
19
20    // Determine the maximum number of consecutive positions required
21    const maxReq = Math.max(...req);
22
23    // Define the modulus for large number outputs
24    const mod = 1e9 + 7;
25
26    // Initialize a 2D array 'f' to store intermediate permutation counts
27    const permutationCounts = Array.from({ length: n }, () => Array(maxReq + 1).fill(0));
28
29    // There's exactly one way to satisfy a sequence of zero elements
30    permutationCounts[0][0] = 1;
31
32    // Iterate over each position from 1 to n-1
33    for (let i = 1; i < n; ++i) {
34        // Define the range for consecutive elements needed
35        let [leftBoundary, rightBoundary] = [0, maxReq];
36
37        // If there's a specific requirement at this position, adjust the boundaries
38        if (req[i] >= 0) {
39            leftBoundary = rightBoundary = req[i];
40        }
41
42        // Calculate the number of valid sequences that can end at position 'i' with 'j' consecutive elements
43        for (let j = leftBoundary; j <= rightBoundary; ++j) {
44            for (let k = 0; k <= Math.min(i, j); ++k) {
45                permutationCounts[i][j] = (permutationCounts[i][j] + permutationCounts[i - 1][j - k]) % mod;
46            }
47        }
48    }
49
50    // Return the permutation count that ends at the last position, subject to the final requirement
51    return permutationCounts[n - 1][req[n - 1]];
52}
53

Time and Space Complexity

The time complexity of the code is O(n * m * min(n, m)), where n is the length of the list req, and m is the maximum number of inversions. The nested loops iterate over each possible pair of indices up to the limitations defined by n, m, and the corresponding conditions in the loops.

The space complexity of the code is O(n * m), which stems from the usage of a 2-dimensional list f with dimensions [n][m+1] to store intermediate computations. Here, m is at most 400, as given by the problem constraints.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What's the relationship between a tree and a graph?

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More