Number of Ways to Rearrange Sticks With K Sticks Visible

How it works

Each row only depends on the previous row, so we can use a 1D array and update it carefully to avoid overwriting values we still need.

Steps

1. Use a 1D DP array of size k + 1.
2. Set dp[1] = 1.
3. For each N from 2 to n:
   • Iterate through K from 1 to k, tracking the previous value before updating.
   • Update dp[K] = (prev + (N-1) * dp[K]) % MOD.
4. Return dp[k].

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.

Things to watch for

Misunderstanding the Recurrence Relation

The key insight is that we place sticks from tallest to shortest. The shortest remaining stick can either be placed at the leftmost position (becoming visible, contributing dfs(N-1, K-1)) or in one of N-1 positions behind a taller stick (contributing (N-1) * dfs(N-1, K)). A common mistake is thinking the multiplier should be N instead of N-1, or confusing which stick is being placed.

Integer Overflow in the Multiplication Term

The term (N-1) * dfs(N-1, K) can cause integer overflow in languages like Java and C++ when both values are large. Always cast to long before multiplication: (long)(N-1) * dfs(N-1, K) % MOD. Failing to do this produces incorrect results for large inputs.

Incorrect Base Cases

The base cases require careful handling. When N == K, all remaining sticks must be visible (return 1). When N == 0 or K == 0 (but not both equal), it is impossible (return 0). A common error is returning 1 when K == 0 regardless of N, or not handling the N == K case before checking K == 0.

Space-Optimized DP Update Order

In the space-optimized version, updating dp[K] requires the old value of dp[K-1] (stored in prev) and the current dp[K]. If you update in the wrong order or forget to save prev before modifying dp[K], you will use already-updated values and get wrong answers. Always save the current value before overwriting: tmp = dp[K]; dp[K] = ...; prev = tmp.

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]

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

        for (int N = 2; N <= n; N++) {
            int prev = 0;
            for (int K = 1; K <= k; K++) {
                int tmp = dp[K];
                dp[K] = (prev + (N - 1) * 1LL * dp[K]) % MOD;
                prev = tmp;
            }
        }

        return dp[k];
    }
};