629. K Inverse Pairs Array - Explanation

1. Dynamic Programming (Top-Down)

Intuition

When placing the number n into a permutation of n - 1 elements, we can create 0 to n - 1 new inverse pairs depending on its position. Placing n at the end creates 0 new pairs, while placing it at the start creates n - 1 pairs since n is larger than all other elements. This gives us a recurrence: the count for (n, k) equals the sum of counts for (n - 1, k), (n - 1, k - 1), ..., (n - 1, k - (n - 1)).

Algorithm

Define count(n, k) as the number of permutations of n elements with exactly k inverse pairs.
Base case: If n == 0, return 1 if k == 0, else return 0.
For each position where we can place n, it creates i inverse pairs (where i goes from 0 to n - 1).
Sum up count(n - 1, k - i) for all valid i.
Cache results to avoid recomputation.

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        MOD = 10**9 + 7
        cache = {}

        def count(n, k):
            if n == 0:
                return 1 if k == 0 else 0
            if k < 0:
                return 0
            if (n, k) in cache:
                return cache[(n, k)]

            cache[(n, k)] = 0
            for i in range(n):
                cache[(n, k)] = (cache[(n, k)] + count(n - 1, k - i)) % MOD

            return cache[(n, k)]

        return count(n, k)

Time & Space Complexity

Time complexity: $O(n ^ 2 * k)$
Space complexity: $O(n * k)$

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

2. Dynamic Programming (Top-Down Optimized)

Intuition

The basic recurrence sums up to n terms. We can optimize using the relationship: count(n, k) = count(n, k - 1) + count(n - 1, k) - count(n - 1, k - n). This comes from observing that count(n, k) and count(n, k - 1) share most terms, differing only at the boundaries. We also add early termination when k exceeds the maximum possible inverse pairs for n elements, which is n * (n - 1) / 2.

Algorithm

Base cases: Return 1 if k == 0, return 0 if n == 1, and handle bounds based on max pairs.
Use the optimized recurrence: count(n, k) = count(n, k - 1) + count(n - 1, k) - count(n - 1, k - n).
The subtraction handles the term that falls outside the valid range when shifting from k - 1 to k.
Apply modular arithmetic to keep numbers manageable.

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        MOD = 10**9 + 7
        dp = [[-1] * (k + 1) for _ in range(n + 1)]

        def count(n, k):
            if k == 0:
                return 1
            if n == 1:
                return 0
            if n * (n - 1) // 2 < k:
                return 0
            if n * (n - 1) // 2 == k:
                return 1
            if dp[n][k] != -1:
                return dp[n][k]

            res = count(n, k - 1)
            if k >= n:
                res -= count(n - 1, k - n)
            res = (res + count(n - 1, k)) % MOD

            dp[n][k] = res
            return res

        return count(n, k)

Time & Space Complexity

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

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

3. Dynamic Programming (Bottom-Up)

Intuition

We build up the solution starting from smaller values of n. For each (N, K) state, we sum contributions from placing element N at different positions, each creating a different number of new inverse pairs. This iterative approach avoids recursion overhead and naturally fills the DP table row by row.

Algorithm

Create a 2D DP table with dp[0][0] = 1.
For each N from 1 to n:
- For each K from 0 to k:
  - Sum up dp[N - 1][K - pairs] for pairs from 0 to N - 1 where K - pairs >= 0.
Return dp[n][k].

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

        for N in range(1, n + 1):
            for K in range(k + 1):
                for pairs in range(N):
                    if K - pairs >= 0:
                        dp[N][K] = (dp[N][K] + dp[N - 1][K - pairs]) % MOD

        return dp[n][k]

Time & Space Complexity

Time complexity: $O(n ^ 2 * k)$
Space complexity: $O(n * k)$

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

4. Dynamic Programming (Bottom-Up Optimized)

Intuition

Rather than summing N terms for each cell, we use the sliding window observation from the top-down optimized approach. The value at dp[N][K] builds on dp[N][K - 1] by adding dp[N - 1][K] (the new term entering the window) and subtracting dp[N - 1][K - N] (the term leaving the window). This reduces each cell computation to constant time.

Algorithm

Create a 2D DP table with dp[0][0] = 1.
For each N from 1 to n, and each K from 0 to k:
- Start with dp[N][K] = dp[N - 1][K].
- If K > 0, add dp[N][K - 1] (cumulative sum from left).
- If K >= N, subtract dp[N - 1][K - N] (remove out-of-window term).
Return dp[n][k].

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

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

        return dp[n][k]

Time & Space Complexity

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

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

5. Dynamic Programming (Space Optimized)

Intuition

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.

Algorithm

Initialize prev array with prev[0] = 1.
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.
Return prev[k].

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]

Time & Space 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.

Common Pitfalls

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.