We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count the Number of Inversions

Difficulty: Hard

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.

Key Insights

  • An inversion is defined as a pair (i, j) where i < j and nums[i] > nums[j].
  • Each requirement specifies a prefix of the permutation and the exact number of inversions that prefix must have.
  • The problem can be approached using dynamic programming to count valid permutations that meet the inversion requirements.

Space and Time Complexity

Time Complexity: O(n^2 * m), where n is the size of the permutation and m is the number of requirements. Space Complexity: O(n * m), for storing the dynamic programming table.

Solution

The solution involves using dynamic programming to count the number of valid permutations. We maintain a DP table where dp[i][j] represents the number of valid permutations of the first i numbers that have exactly j inversions. We iterate through each requirement and update our DP table based on the number of inversions needed for each prefix. The final result is obtained by checking the DP entries corresponding to the last index and the required number of inversions.

Code Solutions

MOD = 10**9 + 7

def countInversions(n, requirements):
    # Initialize the DP table
    dp = [[0] * (400 + 1) for _ in range(n + 1)]
    dp[0][0] = 1  # Base case: 1 way to arrange 0 elements with 0 inversions

    # Fill the DP table
    for i in range(1, n + 1):
        for j in range(i + 1):
            for k in range(j + 1):
                dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD

    # Validate against the requirements
    result = 1
    for end, cnt in requirements:
        if cnt > end * (end + 1) // 2:  # Maximum inversions in a prefix
            return 0
        result = (result * dp[end + 1][cnt]) % MOD

    return result
← Back to All Questions