K Inverse Pairs Array

How it works

Since each row only depends on the previous row, we only need to keep two 1D arrays instead of the full 2D table. We maintain a running total that acts as a prefix sum, adding new values and subtracting values that fall outside the window of size N.

Steps

1. Initialize prev array with prev[0] = 1.
2. For each N from 1 to n:
   • Create a new cur array and maintain a running total.
   • For each K from 0 to k:
     • Add prev[K] to total.
     • If K >= N, subtract prev[K - N] from total.
     • Set cur[K] = total.
   • Swap prev = cur for the next iteration.
3. Return prev[k].

Complexity

• Time complexity: O(n * k)
• Space complexity: O(k)

Where n is the size of the permutation and k is the number of inverse pairs in the permutation.

Things to watch for

Forgetting Modular Arithmetic

Results can grow extremely large, requiring modulo 10^9 + 7 operations. Forgetting to apply the modulo after each addition causes integer overflow. Apply % MOD consistently in all accumulation steps.

Incorrect Handling of Negative Values in Modular Subtraction

When subtracting in the optimized recurrence (res - dp[n-1][k-n]), the result may become negative before taking modulo. Always add MOD before the final modulo: (res - value + MOD) % MOD to ensure a non-negative result.

Not Recognizing the Sliding Window Pattern

The naive approach sums n terms per cell, leading to O(n^2 * k) complexity. The key insight is that consecutive cells share most terms, allowing a sliding window optimization. Missing this pattern results in TLE on large inputs.

Off-by-One Errors in Window Boundaries

When placing element n, it can create 0 to n-1 inverse pairs (not n pairs). The window of previous row values spans k down to k - (n-1). Getting these boundaries wrong produces incorrect counts.

Missing Base Cases

The recurrence requires proper initialization: dp[0][0] = 1 (one way to arrange zero elements with zero pairs). Missing this base case or incorrectly setting dp[n][0] values propagates errors through the entire table.

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        MOD = 10**9 + 7
        prev = [0] * (k + 1)
        prev[0] = 1

        for N in range(1, n + 1):
            cur = [0] * (k + 1)
            total = 0
            for K in range(0, k + 1):
                total = (total + prev[K]) % MOD
                if K >= N:
                    total = (total - prev[K - N] + MOD) % MOD
                cur[K] = total
            prev = cur

        return prev[k]

class Solution {
public:
    int kInversePairs(int n, int k) {
        const int MOD = 1e9 + 7;
        vector<int> prev(k + 1, 0);
        prev[0] = 1;

        for (int N = 1; N <= n; N++) {
            vector<int> cur(k + 1, 0);
            int total = 0;
            for (int K = 0; K <= k; K++) {
                total = (total + prev[K]) % MOD;
                if (K >= N) {
                    total = (total - prev[K - N] + MOD) % MOD;
                }
                cur[K] = total;
            }
            prev = cur;
        }

        return prev[k];
    }
};