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
- Build permutations by inserting the largest element
iinto a permutation of the otheri - 1elements. - 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 toi - 1. - So
dp[i][j] = sum over t of dp[i-1][j-t]fortin[0, i-1], which is a sliding window. - 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
iterms 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], notdp[i-1][j-i+1]. - Forgetting that
nxt[j]depends onnxt[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.