Number of Ways to Rearrange Sticks With K Sticks Visible - Video Solutions

Problem Overview: You are given n sticks with distinct heights from 1 to n. When arranged in a line, a stick becomes visible from the left if it is taller than every stick before it. The task is to count how many permutations of the sticks produce exactly k visible sticks.

Approach 1: Recursive Dynamic Programming with Memoization (Time: O(n*k), Space: O(n*k))

This problem has a classic combinatorics recurrence. When placing the tallest stick among n sticks, two situations occur. If the tallest stick is placed at the front, it will definitely be visible, so the remaining n-1 sticks must produce k-1 visible sticks. If it is placed somewhere else, it will be hidden behind a taller prefix, and you have n-1 possible positions to place it while keeping the visible count unchanged. This gives the recurrence dp[n][k] = dp[n-1][k-1] + (n-1) * dp[n-1][k]. Using recursion with memoization avoids recomputing overlapping states and efficiently evaluates the count modulo 1e9+7. The technique relies heavily on ideas from dynamic programming and combinatorics.

Approach 2: Bottom-Up Dynamic Programming (Time: O(n*k), Space: O(n*k))

The recurrence can be implemented iteratively using a 2D DP table where dp[i][j] represents the number of ways to arrange i sticks so exactly j are visible. Initialize dp[1][1] = 1. For each i from 2 to n, compute values for all valid j. The transition directly follows the recurrence: placing the tallest stick at the front increases visible count, while inserting it in any of the remaining i-1 positions keeps the same visible count. This tabulation method is easier to debug and avoids recursion overhead. It also clearly shows the combinatorial structure of the problem, closely related to permutations studied in math problems.

Approach 3: Space-Optimized Dynamic Programming (Time: O(n*k), Space: O(k))

Each DP row depends only on the previous row. Instead of storing the entire n x k table, maintain two arrays or update a single array from right to left. This reduces memory usage from O(n*k) to O(k) while preserving the same recurrence. The update order is critical to avoid overwriting values that are still needed in the current iteration.

Recommended for interviews: Interviewers typically expect the dynamic programming recurrence. Explaining how the tallest stick either creates a new visible stick or gets hidden shows strong combinatorial reasoning. Implementing the bottom-up DP demonstrates solid problem-solving skills, while mentioning the O(k) space optimization shows deeper mastery.