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

K Inverse Pairs Array

Difficulty: Hard

Problem Description

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

Key Insights

  • The problem can be solved using dynamic programming.
  • The number of inverse pairs increases with the arrangement of numbers.
  • A 2D DP table can be utilized where dp[i][j] represents the number of arrays of size i with exactly j inverse pairs.
  • The transition involves calculating the number of ways to form arrays by considering the current number's position and the previously computed states.

Space and Time Complexity

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

Solution

To solve the problem, we will use a dynamic programming approach. We create a 2D array dp where dp[i][j] denotes the number of arrays of length i with exactly j inverse pairs.

  1. Initialize the base case: An array of length 0 has exactly 0 inverse pairs, so dp[0][0] = 1.
  2. For each length i from 1 to n, compute the number of inverse pairs j from 0 to k.
  3. The value of dp[i][j] can be constructed by summing values from previous lengths considering how the current number can contribute to the inverse pairs.
  4. Specifically, we can use the relationship:
    • dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + ... + dp[i-1][j-i] This means that we can form an array of length i by adding the current number to previous arrays of length i-1, and we need to account for how many new inverse pairs are created depending on the position of the current number.
  5. Finally, return dp[n][k] % (10^9 + 7).

Code Solutions

def kInversePairs(n, k):
    MOD = 10**9 + 7
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    
    for i in range(1, n + 1):
        for j in range(k + 1):
            dp[i][j] = dp[i - 1][j]  # When the current number is at the end
            if j > 0:
                dp[i][j] += dp[i][j - 1]  # Add the last row
            if j >= i:
                dp[i][j] -= dp[i - 1][j - i]  # Remove excess
            dp[i][j] = (dp[i][j] + MOD) % MOD  # Ensure non-negative
    
    return dp[n][k]
← Back to All Questions