⚡Flashcard Drill➔
NeetCode #755LC-629Hard2-D Dynamic Programming
← Back to All Problems

#755 · #629 · K Inverse Pairs Array(K 个逆序对数组)

📌 Problem Statement & Constraints

Given n and k, count the permutations of the integers 1 to n that have exactly k inverse pairs, modulo 1e9+7. An inverse pair is a pair (i, j) with i < j and a[i] > a[j]. Constraints: 1 <= n <= 1000, 0 <= k <= 1000.

💡 Core Algorithmic Approaches

  1. Build permutations by inserting the largest element i into a permutation of the other i - 1 elements.
  2. Placing it at the very end creates 0 new inversions; placing it first creates i - 1; in general it can create any count from 0 to i - 1.
  3. So dp[i][j] = sum over t of dp[i-1][j-t] for t in [0, i-1], which is a sliding window.
  4. Subtracting the window from its shifted self gives dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-i], an O(1) update per state.

💻 Benchmark Python3 Implementation

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        MOD = 10**9 + 7
        dp = [0] * (k + 1)
        dp[0] = 1                      # zero elements, zero inversions
        for i in range(1, n + 1):
            nxt = [0] * (k + 1)
            for j in range(k + 1):
                nxt[j] = dp[j]                     # dp[i-1][j]
                if j > 0:
                    nxt[j] = (nxt[j] + nxt[j - 1]) % MOD
                if j >= i:
                    nxt[j] = (nxt[j] - dp[j - i]) % MOD
            dp = nxt
        return dp[k]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n * k): each state is updated in constant time.
💾 Space Complexity
O(k): one rolling array.

⚠️ Interview Pitfalls & Follow-ups

  • Summing the window of i terms directly: that is O(n * k * i); the sliding-window recurrence makes it O(n * k).
  • Using the wrong subtraction index: the term leaving the window is dp[i-1][j-i], not dp[i-1][j-i+1].
  • Forgetting that nxt[j] depends on nxt[j-1] of the same row: the prefix sum must accumulate within the current layer.
  • Handling k = 0: the answer is 1 (only the sorted permutation), which the base case provides.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems