Here’s the Java solution for LeetCode 629. K Inverse Pairs Array, including both the standard prefix-sum version and a rolling-window variant.
Problem
Given n and k, count the number of permutations of 1…n that contain exactly k inverse pairs (a pair (i, j) with i < j and nums[i] > nums[j]). Return the result modulo 10^9 + 7.
Examples
- n = 3, k = 0 → 1 (only [1,2,3])
- n = 3, k = 1 → 2 ([1,3,2], [2,1,3])
- n = 3, k = 3 → 0
Core Recurrence
Insert the largest number i into a permutation of 1…i-1. Placing it at position p from the end creates exactly p new inverse pairs, where p ranges over 0 … i-1. Therefore:
dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + … + dp[i-1][j-(i-1)]
Naively this is O(n·k²). Using a prefix sum (or sliding window) turns each transition into O(1), giving O(n·k).
Solution 1 — Prefix Sum + Two Rows
class Solution {
private static final int MOD = 1_000_000_007;
public int kInversePairs(int n, int k) { long[] prev = new long[k + 1]; prev[0] = 1; // n = 1 -> only 0 inverse pairs for (int i = 2; i <= n; i++) { long[] prefix = new long[k + 1]; prefix[0] = prev[0]; for (int j = 1; j <= k; j++) { prefix[j] = (prefix[j - 1] + prev[j]) % MOD; } long[] curr = new long[k + 1]; for (int j = 0; j <= k; j++) { long sum = prefix[j]; // sum of prev[0..j] if (j - i >= 0) { // subtract prev[0..j-i] sum = (sum - prefix[j - i] + MOD) % MOD; } curr[j] = sum; } prev = curr; } return (int) prev[k]; }}
Solution 2 — Sliding Window (no prefix array)
class Solution {
private static final int MOD = 1_000_000_007;
public int kInversePairs(int n, int k) { long[] dp = new long[k + 1]; dp[0] = 1; for (int i = 2; i <= n; i++) { long[] next = new long[k + 1]; long window = 0; for (int j = 0; j <= k; j++) { window = (window + dp[j]) % MOD; // add right end if (j - i >= 0) { window = (window - dp[j - i] + MOD) % MOD; // drop left end } next[j] = window; } dp = next; } return (int) dp[k]; }}
Walkthrough (n = 3, k = 1)
i dp array (j = 0…1) meaning
1 [1, 0] [1]
2 [1, 1] [1,2], [2,1]
3 [1, 2] answer for k = 1 is 2
Complexity
- Time: O(n × k)
- Space: O(k)
Interview Notes
- Mention the naive O(n·k²) version first, then explain the prefix-sum / sliding-window optimization — that transition is usually what the interviewer is looking for.
- Use long for intermediate values to avoid overflow before taking the modulo, and add MOD before % when subtracting to keep values non-negative.
- A useful early exit: if k > n * (n - 1) / 2, the answer is 0.
Want me to add a version that also prints the actual permutations for small n, or a top-down memoized variant for comparison?
