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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count the Number of Inversions

Number: 3460

Difficulty: Hard

Paid? No

Companies: Amazon, Salesforce

Problem Description

Given an integer n and a list of requirements, where each requirement is a pair [end, cnt] meaning that the prefix of the permutation from index 0 to end must have exactly cnt inversions, count the number of permutations of [0, 1, 2, …, n - 1] that satisfy all these prefix inversion requirements. An inversion in an array is a pair (i, j) such that i < j and nums[i] > nums[j]. Return the count modulo 10^9 + 7.

Key Insights

  • A classical DP exists that counts the number of permutations with a given total inversion count.
  • Use the recurrence: dp[i+1][k] = sum(dp[i][k - j]) for j = 0 to i (each j represents the number of additional inversions when placing a new element).
  • Only prefixes with specific lengths (i = end+1) have inversion requirements and must be filtered to allow only the required inversion count.
  • Since requirements’ inversion counts are at most 400, we restrict our DP dimension in the inversion direction to 401.
  • The answer is given by dp[n] evaluated at the inversion count specified by the requirement for the full permutation (since at least one requirement is on the full array).

Space and Time Complexity

Time Complexity: O(n^2 * maxInv), where n is the number of elements (n ≤ 300) and maxInv is 401. Space Complexity: O(n * maxInv) or O(maxInv) if we optimize by using a single DP array.

Solution

We use dynamic programming to solve the problem. The main idea is to build the permutation one element at a time while tracking the total number of inversions so far. Let dp[i][inv] be the number of ways to arrange i elements with exactly inv inversions. When we place a new element into the permutation (which will make the prefix length i+1), the new element can be inserted in any of the (i+1) possible positions. Inserting at position j contributes j new inversions because it “jumps over” j elements that are larger (by the properties of permutations of distinct integers). Hence, the recurrence relation:   dp[i + 1][inv + j] += dp[i][inv] for j from 0 to i. The twist is that when the prefix length (i+1) equals one of the required indices (given by end+1), we must only keep the state that exactly equals the given inversion count (cnt). This filtering is applied after processing each prefix length. We accumulate the DP transitions while performing the required filtering on the fly. Finally, we return the number of ways modulo 10^9 + 7 for the full permutation that meets the required inversion count.

Code Solutions

MOD = 10**9 + 7

def countInversionPermutations(n, requirements):
    # Build a mapping from prefix length (end+1) to required inversion count.
    req = {}
    for end, cnt in requirements:
        req[end + 1] = cnt

    maxInv = 400  # Only need to track inversion counts up to 400
    # Initialize dp for 0 elements: only 0 inversions.
    dp = [0] * (maxInv + 1)
    dp[0] = 1

    # Iterate over prefix lengths 0 to n-1, building dp for prefix length i+1.
    for i in range(0, n):
        next_dp = [0] * (maxInv + 1)
        # For each possible inversion count state for prefix of length i.
        for inv in range(maxInv + 1):
            if dp[inv]:
                # Insert a new element into any of i+1 positions.
                for j in range(0, i+1):
                    new_inv = inv + j
                    if new_inv <= maxInv:
                        next_dp[new_inv] = (next_dp[new_inv] + dp[inv]) % MOD
        # If there is a requirement for prefix length i+1, filter the dp.
        if (i+1) in req:
            required_inv = req[i+1]
            filtered = [0] * (maxInv + 1)
            filtered[required_inv] = next_dp[required_inv]
            next_dp = filtered
        dp = next_dp
    # The complete permutation is length n. The requirement must exist for n.
    # Answer is the dp state at the required inversion count.
    return dp[ req[n] ] if n in req else sum(dp) % MOD

# Example usage:
if __name__ == "__main__":
    n = 3
    requirements = [[2,2],[0,0]]
    print(countInversionPermutations(n, requirements))  # Expected output: 2
← Back to All Questions