Number of Ways to Rearrange Sticks With K Sticks Visible

Number of Ways to Rearrange Sticks With K Sticks Visible

What is this problem about?

The Number of Ways to Rearrange Sticks With K Sticks Visible problem places n sticks of distinct heights in a line. A stick is visible from the left if it's taller than all sticks to its left. Count arrangements where exactly k sticks are visible from the left. This hard combinatorics/DP problem is related to unsigned Stirling numbers of the first kind.

Why is this asked in interviews?

Google asks this because it requires recognizing the connection to Stirling numbers — a non-trivial combinatorial insight. The DP recurrence is elegant: dp[n][k] = dp[n-1][k-1] + (n-1)*dp[n-1][k]. The math, combinatorics, and dynamic programming interview pattern is the core.

Algorithmic pattern used

Stirling number DP. dp[n][k] = ways to arrange n sticks with exactly k visible. When placing the n-th stick (tallest): if placed first (leftmost), it's visible → dp[n-1][k-1] ways for remaining. If placed anywhere else (n-1 positions), it's never visible (it's tallest but not leftmost... wait: actually it's always visible if placed anywhere since it's tallest. Hmm, the correct recurrence involves the smallest stick).

Correct recurrence: dp[n][k] = dp[n-1][k-1] + (n-1)*dp[n-1][k]. The smallest stick is either placed leftmost (it's always visible, and visibility of others is dp[n-1][k-1]) or placed anywhere else (n-1 positions; it never blocks visibility, dp[n-1][k]).

Example explanation

dp[1][1]=1. dp[2][1]=1 (both see only 1st), dp[2][2]=1 (both visible if ascending). dp[3][1]: dp[2][0]+2dp[2][1]=0+2=2. dp[3][2]: dp[2][1]+2dp[2][2]=1+2=3. dp[3][3]: dp[2][2]+2*dp[2][3]=1+0=1. n=3,k=2 → 3. Arrangements: [3,1,2],[2,1,3],[1,2,3]? No. [3,1,2]: visible=3 (only 3). Wait need to recount. dp[3][2]=3. Correct.

Common mistakes candidates make

• Off-by-one in DP state indexing (1-indexed vs 0-indexed).
• Not applying modular arithmetic.
• Using the wrong recurrence (placing the largest vs smallest stick first).
• Confusing visible-from-left with visible-from-right.

Interview preparation tip

Stirling numbers appear in "count permutations with k specific property" problems (left-to-right maxima, cycles, etc.). Recognizing the recurrence f(n,k) = f(n-1,k-1) + (n-1)*f(n-1,k) is the key. Practice "count permutations with exactly k left-to-right maxima/minima" problems — they all use this recurrence. Relating combinatorial counting problems to known sequences (Stirling, Catalan, Bell) is a high-value skill for Google-level interviews.