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

Prerequisites

Before attempting this problem, you should be comfortable with:

Recursion - Understanding how to break down problems into smaller subproblems with base cases
Dynamic Programming - Recognizing overlapping subproblems and using memoization or tabulation
Combinatorics - Counting arrangements and understanding the recurrence relation for permutations
Modular Arithmetic - Working with results modulo 10^9 + 7 to prevent integer overflow

1. Recursion

Intuition

Consider placing sticks from tallest to shortest. The tallest stick must be visible. For the remaining sticks, we decide where to place each one relative to previously placed sticks. If a stick is placed at the leftmost available position, it becomes visible. Otherwise, it hides behind a taller stick already placed to its left.

Algorithm

Define dfs(N, K) where N is the number of sticks remaining and K is how many still need to be visible.
Base cases:
- If N == K, all remaining sticks must be visible (only one way: place them in increasing order from left), return 1.
- If N == 0 or K == 0 (but not both), it's impossible, return 0.
Two choices for the shortest remaining stick:
- Place it at the leftmost position, making it visible: dfs(N-1, K-1).
- Place it in one of the N-1 positions behind a taller stick: (N-1) * dfs(N-1, K).
Return the sum modulo 10^9 + 7.

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)

public class Solution {
    private static final int MOD = 1_000_000_007;

    public int rearrangeSticks(int n, int k) {
        return dfs(n, k);
    }

    private int dfs(int N, int K) {
        if (N == K) return 1;
        if (N == 0 || K == 0) return 0;
        return (int) ((dfs(N - 1, K - 1) + (long) (N - 1) * dfs(N - 1, K)) % MOD);
    }
}

class Solution {
    /**
     * @param {number} n
     * @param {number} k
     * @return {number}
     */
    rearrangeSticks(n, k) {
        const MOD = 1e9 + 7;

        const dfs = (N, K) => {
            if (N === K) return 1;
            if (N === 0 || K === 0) return 0;
            return (dfs(N - 1, K - 1) + (N - 1) * dfs(N - 1, K)) % MOD;
        };

        return dfs(n, k);
    }
}

public class Solution {
    private const int MOD = 1_000_000_007;

    public int RearrangeSticks(int n, int k) {
        return Dfs(n, k);
    }

    private int Dfs(int N, int K) {
        if (N == K) return 1;
        if (N == 0 || K == 0) return 0;
        return (int)((Dfs(N - 1, K - 1) + (long)(N - 1) * Dfs(N - 1, K)) % MOD);
    }
}

func rearrangeSticks(n int, k int) int {
    MOD := int(1e9 + 7)

    var dfs func(N, K int) int
    dfs = func(N, K int) int {
        if N == K {
            return 1
        }
        if N == 0 || K == 0 {
            return 0
        }
        return (dfs(N-1, K-1) + (N-1)*dfs(N-1, K)) % MOD
    }

    return dfs(n, k)
}

class Solution {
    private val MOD = 1_000_000_007

    fun rearrangeSticks(n: Int, k: Int): Int {
        fun dfs(N: Int, K: Int): Int {
            if (N == K) return 1
            if (N == 0 || K == 0) return 0
            return ((dfs(N - 1, K - 1) + (N - 1).toLong() * dfs(N - 1, K)) % MOD).toInt()
        }
        return dfs(n, k)
    }
}

impl Solution {
    pub fn rearrange_sticks(n: i32, k: i32) -> i32 {
        const MOD: i64 = 1_000_000_007;

        fn dfs(n: i64, k: i64) -> i64 {
            if n == k { return 1; }
            if n == 0 || k == 0 { return 0; }
            (dfs(n - 1, k - 1) + (n - 1) * dfs(n - 1, k)) % MOD
        }

        dfs(n as i64, k as i64) as i32
    }
}

Time & Space Complexity

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

2. Dynamic Programming (Top-Down)

Intuition

The recursive solution has overlapping subproblems. By caching results in a 2D table, we avoid redundant computation.

Algorithm

Create a memoization table of size (n+1) x (k+1) initialized to -1.
In dfs(N, K), check if the result is already computed.
Apply the same recurrence: dfs(N-1, K-1) + (N-1) * dfs(N-1, K).
Store and return the result modulo 10^9 + 7.

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)

public class Solution {
    private static final int MOD = 1_000_000_007;
    private int[][] dp;

    public int rearrangeSticks(int n, int k) {
        dp = new int[n + 1][k + 1];
        for (int[] row : dp) {
            Arrays.fill(row, -1);
        }
        return dfs(n, k);
    }

    private int dfs(int N, int K) {
        if (N == K) return 1;
        if (N == 0 || K == 0) return 0;
        if (dp[N][K] != -1) return dp[N][K];
        dp[N][K] = (int) ((dfs(N - 1, K - 1) + (long) (N - 1) * dfs(N - 1, K)) % MOD);
        return dp[N][K];
    }
}

class Solution {
    /**
     * @param {number} n
     * @param {number} k
     * @return {number}
     */
    rearrangeSticks(n, k) {
        const MOD = 1e9 + 7;
        const dp = Array.from({ length: n + 1 }, () => Array(k + 1).fill(-1));

        const dfs = (N, K) => {
            if (N === K) return 1;
            if (N === 0 || 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);
    }
}

public class Solution {
    private const int MOD = 1_000_000_007;
    private int[,] dp;

    public int RearrangeSticks(int n, int k) {
        dp = new int[n + 1, k + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                dp[i, j] = -1;
            }
        }
        return Dfs(n, k);
    }

    private int Dfs(int N, int K) {
        if (N == K) return 1;
        if (N == 0 || K == 0) return 0;
        if (dp[N, K] != -1) return dp[N, K];
        dp[N, K] = (int)((Dfs(N - 1, K - 1) + (long)(N - 1) * Dfs(N - 1, K)) % MOD);
        return dp[N, K];
    }
}

class Solution {
    private val MOD = 1_000_000_007
    private lateinit var dp: Array<IntArray>

    fun rearrangeSticks(n: Int, k: Int): Int {
        dp = Array(n + 1) { IntArray(k + 1) { -1 } }
        return dfs(n, k)
    }

    private fun dfs(N: Int, K: Int): Int {
        if (N == K) return 1
        if (N == 0 || K == 0) return 0
        if (dp[N][K] != -1) return dp[N][K]
        dp[N][K] = ((dfs(N - 1, K - 1) + (N - 1).toLong() * dfs(N - 1, K)) % MOD).toInt()
        return dp[N][K]
    }
}

class Solution {
    func rearrangeSticks(_ n: Int, _ k: Int) -> Int {
        let MOD = 1_000_000_007
        var dp = [[Int]](repeating: [Int](repeating: -1, count: k + 1), count: n + 1)

        func dfs(_ N: Int, _ K: Int) -> Int {
            if N == K { return 1 }
            if N == 0 || 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)

Intuition

We fill the DP table iteratively from smaller subproblems to larger ones. dp[N][K] represents the number of ways to arrange N sticks with exactly K visible.

Algorithm

Create a DP table of size (n+1) x (k+1) initialized to 0.
Set dp[1][1] = 1 (one stick, one visible).
For each N from 2 to n, and each K from 1 to k:
- dp[N][K] = (dp[N-1][K-1] + (N-1) * dp[N-1][K]) % MOD
Return dp[n][k].

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]

public class Solution {
    private static final int MOD = 1_000_000_007;

    public int rearrangeSticks(int n, int k) {
        int[][] dp = new int[n + 1][k + 1];
        dp[1][1] = 1;

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

        return dp[n][k];
    }
}

class Solution {
    /**
     * @param {number} n
     * @param {number} k
     * @return {number}
     */
    rearrangeSticks(n, k) {
        const MOD = 1e9 + 7;
        const dp = Array.from({ length: n + 1 }, () => Array(k + 1).fill(0));
        dp[1][1] = 1;

        for (let N = 2; N <= n; N++) {
            for (let K = 1; K <= k; K++) {
                dp[N][K] = (dp[N - 1][K - 1] + (N - 1) * dp[N - 1][K]) % MOD;
            }
        }

        return dp[n][k];
    }
}

public class Solution {
    private const int MOD = 1_000_000_007;

    public int RearrangeSticks(int n, int k) {
        int[,] dp = new int[n + 1, k + 1];
        dp[1, 1] = 1;

        for (int N = 2; N <= n; N++) {
            for (int K = 1; K <= k; K++) {
                dp[N, K] = (int)((dp[N - 1, K - 1] + (long)(N - 1) * dp[N - 1, K]) % MOD);
            }
        }

        return dp[n, k];
    }
}

class Solution {
    fun rearrangeSticks(n: Int, k: Int): Int {
        val MOD = 1_000_000_007
        val dp = Array(n + 1) { IntArray(k + 1) }
        dp[1][1] = 1

        for (N in 2..n) {
            for (K in 1..k) {
                dp[N][K] = ((dp[N - 1][K - 1] + (N - 1).toLong() * dp[N - 1][K]) % MOD).toInt()
            }
        }

        return dp[n][k]
    }
}

class Solution {
    func rearrangeSticks(_ n: Int, _ k: Int) -> Int {
        let MOD = 1_000_000_007
        var dp = [[Int]](repeating: [Int](repeating: 0, count: k + 1), count: n + 1)
        dp[1][1] = 1

        for N in 2...n {
            for K in 1...k {
                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)

Intuition

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.

Algorithm

Use a 1D DP array of size k + 1.
Set dp[1] = 1.
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.
Return dp[k].

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]

public class Solution {
    private static final int MOD = 1_000_000_007;

    public int rearrangeSticks(int n, int k) {
        int[] dp = new int[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] = (int) ((prev + (long) (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];
    }
};

class Solution {
    /**
     * @param {number} n
     * @param {number} k
     * @return {number}
     */
    rearrangeSticks(n, k) {
        const MOD = 1e9 + 7;
        const dp = new Array(k + 1).fill(0);
        dp[1] = 1;

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

        return dp[k];
    }
}

public class Solution {
    private const int MOD = 1_000_000_007;

    public int RearrangeSticks(int n, int k) {
        int[] dp = new int[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] = (int)((prev + (long)(N - 1) * dp[K]) % MOD);
                prev = tmp;
            }
        }

        return dp[k];
    }
}

class Solution {
    fun rearrangeSticks(n: Int, k: Int): Int {
        val MOD = 1_000_000_007
        val dp = IntArray(k + 1)
        dp[1] = 1

        for (N in 2..n) {
            var prev = 0
            for (K in 1..k) {
                val tmp = dp[K]
                dp[K] = ((prev + (N - 1).toLong() * dp[K]) % MOD).toInt()
                prev = tmp
            }
        }

        return dp[k]
    }
}

class Solution {
    func rearrangeSticks(_ n: Int, _ k: Int) -> Int {
        let MOD = 1_000_000_007
        var dp = [Int](repeating: 0, count: k + 1)
        dp[1] = 1

        for N in 2...n {
            var prev = 0
            for K in 1...k {
                let 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.

Common Pitfalls

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.