1866. Number of Ways to Rearrange Sticks With K Sticks Visible - Explanation

1. Recursion

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

        def dfs(N, K):
            if N == K:
                return 1
            if N == 0 or K == 0:
                return 0
            return (dfs(N - 1, K - 1) + (N - 1) * dfs(N - 1, K)) % MOD

        return dfs(n, k)

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(n)$ for recursion stack.

2. Dynamic Programming (Top-Down)

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

        def dfs(N, K):
            if N == K:
                return 1
            if N == 0 or K == 0:
                return 0
            if dp[N][K] != -1:
                return dp[N][K]
            dp[N][K] = (dfs(N - 1, K - 1) + (N - 1) * dfs(N - 1, K)) % MOD
            return dp[N][K]

        return dfs(n, k)

Time & Space Complexity

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

Where $n$ represents the total number of sticks, and $k$ denotes the number of sticks that must be visible from the left side.

3. Dynamic Programming (Bottom-Up)

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

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

        return dp[n][k]

Time & Space Complexity

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

Where $n$ represents the total number of sticks, and $k$ denotes the number of sticks that must be visible from the left side.

4. Dynamic Programming (Space Optimized)

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

        for N in range(2, n + 1):
            prev = 0
            for K in range(1, k + 1):
                tmp = dp[K]
                dp[K] = (prev + (N - 1) * dp[K]) % MOD
                prev = tmp

        return dp[k]

Time & Space Complexity

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

Where $n$ represents the total number of sticks, and $k$ denotes the number of sticks that must be visible from the left side.