Number of Ways to Rearrange Sticks With K Sticks Visible

You have n uniquely-sized sticks, numbered 1 through n by height. You need to arrange all n sticks in a row such that exactly k sticks are visible when viewed from the left. A stick is visible if there is no taller stick to its left. Return the number of such arrangements, modulo 10^9 + 7.

This is LeetCode 1866: Number of Ways to Rearrange Sticks With K Sticks Visible, and it is a beautiful example of how a combinatorial counting problem reduces to a clean DP recurrence. The key insight connects this problem to a well-known mathematical object: the unsigned Stirling numbers of the first kind.

Why this problem matters

This problem teaches you a powerful technique for combinatorial DP: instead of trying to enumerate arrangements directly, you focus on where one specific element can go. That single decision splits the problem into cases that map cleanly onto smaller subproblems. You will see this same "place one element and recurse" strategy in problems about permutations, partitions, and sequence counting.

It also introduces you to Stirling numbers, which appear more often in competitive programming and interviews than most people expect. Once you recognize the pattern, a whole family of counting problems becomes approachable.

The approach

The trick is to think about the shortest stick, the one with height 1. This stick has a special property: it can never block any other stick, because every other stick is taller than it.

There are exactly two cases for where stick 1 can go:

Case A: Stick 1 goes in the leftmost position. Since it is the shortest, nothing blocks it, so it is always visible. You now need to arrange the remaining n - 1 sticks so that exactly k - 1 of them are visible. That gives dp[n-1][k-1] arrangements.

Case B: Stick 1 goes in any non-leftmost position. There are n - 1 such positions. No matter which one you pick, some taller stick will always be to its left, so stick 1 is never visible. The remaining n - 1 sticks still need to produce exactly k visible sticks. That gives (n - 1) * dp[n-1][k] arrangements.

Combining both cases:

dp[n][k] = dp[n-1][k-1] + (n-1) * dp[n-1][k]

This is exactly the recurrence for the unsigned Stirling numbers of the first kind. The base case is dp[1][1] = 1 (one stick, one visible), and dp[n][0] = 0 for all n >= 1 (you cannot have zero visible sticks with at least one stick).

The solution

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

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

    return dp[n][k]

Step-by-step walkthrough

Let's verify the result by thinking about it concretely. With n = 4 sticks and k = 2 visible, we computed dp[4][2] = 11. Each row of the table builds on the previous one, and the two terms in the recurrence correspond to the two cases: "shortest stick is visible at the front" and "shortest stick is hidden somewhere else."

The (n - 1) multiplier in the second term accounts for the number of non-front positions where the shortest stick can hide. This is what makes the recurrence grow quickly and why the modular arithmetic matters for large inputs.

Complexity analysis

Since each cell depends only on the row above, you can optimize space to O(k) by keeping just two rows. Here is the optimized version:

def rearrangeSticks(n, k):
    MOD = 10**9 + 7
    prev = [0] * (k + 1)
    prev[1] = 1

    for i in range(2, n + 1):
        curr = [0] * (k + 1)
        for j in range(1, min(i, k) + 1):
            curr[j] = (prev[j - 1] + (i - 1) * prev[j]) % MOD
        prev = curr

    return prev[k]

The building blocks

Combinatorial DP via element placement

The core technique here is choosing one specific element (the shortest stick), reasoning about where it can go, and reducing each case to a smaller subproblem. This "place one element" strategy is a general-purpose tool for counting problems on permutations.

The same idea applies whenever you have n distinct objects and want to count arrangements with some structural constraint. Pick the smallest (or largest, or most constrained) element, figure out its valid positions, and write a recurrence based on those positions.

Unsigned Stirling numbers of the first kind

The values dp[n][k] in this problem are exactly the unsigned Stirling numbers of the first kind, written c(n, k) or [n k]. These count the number of permutations of n elements with exactly k cycles. The connection to visible sticks comes from the fact that each "visible stick" corresponds to a cycle leader in the permutation's cycle decomposition.

You do not need to know Stirling numbers to solve this problem. The DP recurrence is derivable purely from the stick-placement argument. But recognizing the connection helps if you encounter related counting problems in the future.

Edge cases

Before submitting, make sure your solution handles these:

• k = n: Only one arrangement works, where all sticks are in increasing order (every stick is visible). dp[n][n] = 1.
• k = 1: Only the tallest stick is visible, meaning it must be first. The remaining n - 1 sticks can go in any order. dp[n][1] = (n - 1)!.
• k = 0: Impossible when n >= 1. At least the tallest stick is always visible. dp[n][0] = 0.
• n = 1, k = 1: The single stick is always visible. Return 1.
• Large n and k: With n up to 1000, the O(n * k) solution runs comfortably within time limits. Just remember the modular arithmetic.

From understanding to recall

You have worked through the recurrence, traced the table, and seen how the "place the shortest stick" argument drives the entire solution. The logic makes sense now. But the gap between understanding and recall is real. In an interview, you need to derive this recurrence from scratch, not just nod along when someone explains it.

Spaced repetition closes that gap. The first time you revisit this problem, you might need a minute to remember why the shortest stick is the right element to focus on. The second time, the two cases (front vs. elsewhere) come back quickly. By the third or fourth review, the recurrence writes itself.

The "place one element and recurse" pattern is one of the building blocks that shows up across many counting problems. Drilling it until the technique is automatic means you will recognize it instantly when a new problem uses the same structure.

Related posts

• Unique Paths - DP grid counting with a similar table-filling approach
• Climbing Stairs - The classic DP recurrence that teaches the recursion-to-table pipeline
• Permutation Sequence - Permutation counting using factorial number systems

The best way to internalize hard DP patterns like this one is not to grind dozens of similar problems back to back. It is to solve the problem once with deep understanding, then revisit it at spaced intervals until the recurrence and the reasoning behind it are second nature. That is the approach that turns "I have seen this before" into "I know exactly how to solve this."