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

K Inverse Pairs Array

Number: 629

Difficulty: Hard

Paid? No

Companies: Microsoft, Meta, Bloomberg, Amazon, Works Applications

Problem Description

Given two integers n and k, count the number of different arrays consisting of numbers from 1 to n such that there are exactly k inverse pairs (an inverse pair is a pair of indices [i, j] where 0 <= i < j < n and nums[i] > nums[j]). Since the answer can be huge, return it modulo 10^9 + 7.

Key Insights

  • Understand that an inverse pair is created when a larger number appears before a smaller number.
  • Use dynamic programming considering the recurrence: dp[i][j] = sum(dp[i-1][j - r]) for r from 0 to min(j, i-1).
  • Recognize that the naive DP transition can be optimized with prefix sums to reduce time complexity.
  • Only the previous row of the DP table is needed at any time, enabling space optimization.

Space and Time Complexity

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

Solution

The solution leverages dynamic programming. Define dp[i][j] as the number of arrays using numbers 1 to i with exactly j inverse pairs. For a new number i, when inserted into every possible position of the array formed by numbers 1 to i-1, it creates different amounts of new inverse pairs depending on the insertion position. The recurrence relation is expressed as:

dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + ... + dp[i-1][j - (i-1)],

for valid indices, where dp[i-1][x] is considered 0 when x is negative.
To avoid recomputing the sum in the recurrence, we compute prefix sums over dp[i-1][:]. This turns the inner loop into an O(1) operation by subtracting the cumulative sum at j-i from the cumulative sum at j. Finally, each dp[i][j] calculation is taken modulo 10^9+7. This DP approach efficiently handles the constraints.

Code Solutions

MOD = 10**9 + 7

def kInversePairs(n: int, k: int) -> int:
    # dp[j] will represent the number of arrays using current numbers with exactly j inverse pairs
    dp = [0] * (k + 1)
    dp[0] = 1  # With one number, there is exactly 0 inverse pair
    # Loop for each number from 2 to n
    for i in range(2, n + 1):
        # new_dp will hold the results for using numbers [1...i]
        new_dp = [0] * (k + 1)
        # prefix sum initialization
        prefix = [0] * (k + 1)
        prefix[0] = dp[0]
        for j in range(1, k + 1):
            prefix[j] = (prefix[j - 1] + dp[j]) % MOD
        # Compute new_dp using the prefix sums
        for j in range(0, k + 1):
            # For each j, determine valid range of values that contribute
            # dp[i][j] = prefix[j] - (prefix[j-i] if j >= i else 0)
            new_dp[j] = prefix[j] if j < i else (prefix[j] - prefix[j - i]) % MOD
        dp = new_dp  # update dp for next iteration
    return dp[k] % MOD

# Example test cases
print(kInversePairs(3, 0))  # Output: 1, only sorted [1,2,3] exists.
print(kInversePairs(3, 1))  # Output: 2, arrays [1,3,2] and [2,1,3] have exactly 1 inverse pair.
← Back to All Questions