Here’s the Java solution for LeetCode 629. K Inverse Pairs Array, including both the standard prefix-sum version and a rolling-window variant.ProblemGiven 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.Examplesn 3, k 0 → 1 (only [1,2,3])n 3, k 1 → 2 ([1,3,2], [2,1,3])n 3, k 3 → 0Core RecurrenceInsert 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 Rowsclass 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) meaning1 [1, 0] [1]2 [1, 1] [1,2], [2,1]3 [1, 2] answer for k 1 is 2ComplexityTime: O(n × k)Space: O(k)Interview NotesMention 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?
