K Inverse Pairs Array — Solution in Python, Java & C++
K Inverse Pairs Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
K Inverse Pairs Array is a hard coding problem on dynamic programming and prefix sum, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Dynamic Programming, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An inverse pair of an array nums is a pair of indices (i, j) with 0 <= i < j < nums.length and nums[i] > nums[j].
Given n and k, count the arrangements (permutations) of the numbers 1 to n that contain exactly k inverse pairs. The count can be huge, so return it modulo 10^9 + 7.
Example 1
Input: n = 3, k = 0
Output: 1
Explanation: Only [1,2,3] has no inverse pair.
Example 2
Input: n = 3, k = 1
Output: 2
Explanation: [1,3,2] and [2,1,3].
Example 3
Input: n = 4, k = 2
Output: 5
Explanation: [1,3,4,2], [1,4,2,3], [2,1,4,3], [2,3,1,4] and [3,1,2,4].
Constraints
1 <= n <= 10000 <= k <= 1000
Hints for K Inverse Pairs Array
Hint 1
Build the permutation by inserting the numbers in increasing order. Where can
ngo, and how many new inverse pairs does each spot create?Hint 2
Placing
nwithtnumbers after it creates exactlytnew pairs, fort = 0 … n - 1, and it never changes the pairs among the smaller numbers. Sodp[n][k] = dp[n-1][k] + dp[n-1][k-1] + … + dp[n-1][k-n+1].Hint 3
That sum is a sliding window over the previous row: keep a running total, add
dp[n-1][k]and subtractdp[n-1][k-n], so each entry costsO(1). Mind the modulus when subtracting.
How to solve K Inverse Pairs Array
Removing the largest value from a permutation of 1..n leaves a permutation of 1..n-1, and the largest value contributes exactly as many inverse pairs as there are elements after it (0 to n - 1). So the counts for n are window sums of the counts for n - 1.
Approach
- Start from
dp = [1, 0, 0, …](one arrangement of zero numbers, with zero pairs). - For
i = 1 … n, buildnext[j] = dp[j] + dp[j-1] + … + dp[j-i+1](indices below 0 ignored) as a running window sum: adddp[j], and oncej >= isubtractdp[j - i]. - Reduce every value modulo
10^9 + 7, adding the modulus back after a subtraction. - Return
dp[k]after the last row.
Why it works
The map "permutation of 1..i ↦ (permutation of 1..i-1 with i removed, number of elements after i)" is a bijection onto pairs (permutation, t) with 0 <= t <= i - 1, and the inverse-pair count of the original is the smaller permutation's count plus t. Summing over t gives the window recurrence, and the running sum computes each window in constant time.
Complexity
- Time —
O(n * k) - Space —
O(k)
Pitfalls
- The plain recurrence with an inner loop over
tisO(n * k * n)— too slow atn = k = 1000. - After
(window - dp[j - i])the value can go negative: add10^9 + 7before taking the remainder. - Values of
kaboven(n-1)/2are impossible and correctly come out as0.
Reference solution
Python
def kInversePairs(n: int, k: int) -> int:
MOD = 10**9 + 7
dp = [0] * (k + 1)
dp[0] = 1
for i in range(1, n + 1):
nxt = [0] * (k + 1)
window = 0
for j in range(k + 1):
window += dp[j]
if j >= i:
window -= dp[j - i]
window %= MOD
nxt[j] = window
dp = nxt
return dp[k]Java
public static int kInversePairs(int n, int k) {
final long MOD = 1000000007L;
long[] dp = new long[k + 1];
dp[0] = 1;
for (int i = 1; i <= n; i++) {
long[] next = new long[k + 1];
long window = 0;
for (int j = 0; j <= k; j++) {
window = (window + dp[j]) % MOD;
if (j >= i) window = (window - dp[j - i] + MOD) % MOD;
next[j] = window;
}
dp = next;
}
return (int) dp[k];
}C++
int kInversePairs(int n, int k) {
const long long MOD = 1000000007LL;
vector<long long> dp(k + 1, 0);
dp[0] = 1;
for (int i = 1; i <= n; i++) {
vector<long long> next(k + 1, 0);
long long window = 0;
for (int j = 0; j <= k; j++) {
window = (window + dp[j]) % MOD;
if (j >= i) window = (window - dp[j - i] + MOD) % MOD;
next[j] = window;
}
dp = next;
}
return (int) dp[k];
}JavaScript
var kInversePairs = function(n, k) {
var MOD = 1000000007;
var dp = new Array(k + 1).fill(0);
dp[0] = 1;
for (var i = 1; i <= n; i++) {
var next = new Array(k + 1).fill(0);
var window = 0;
for (var j = 0; j <= k; j++) {
window = (window + dp[j]) % MOD;
if (j >= i) window = (window - dp[j - i] + MOD) % MOD;
next[j] = window;
}
dp = next;
}
return dp[k];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming · Prefix Sum