629. K Inverse Pairs Array - Explanation

1. Dynamic Programming (Top-Down)

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)

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)

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)

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)

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.