Number of Ways to Rearrange Sticks With K Sticks Visible — Hard Problem & Solution

There are n sticks of distinct lengths 1 through n. Arrange them in a row; a stick is visible from the left when every stick before it is shorter.

Difficulty: Hard
Topics: Math, Dynamic Programming, Combinatorics
Asked at: Amazon, Google, Meta
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

There are n sticks of distinct lengths 1 through n. Arrange them in a row; a stick is visible from the left when every stick before it is shorter.

Return the number of arrangements in which exactly k sticks are visible, modulo 10⁹ + 7.

Example 1

Input: n = 3, k = 2
Output: 3
Explanation: `[1,3,2]`, `[2,3,1]` and `[2,1,3]`.

Example 2

Input: n = 5, k = 5
Output: 1
Explanation: Only the fully sorted arrangement shows all five.

Example 3

Input: n = 20, k = 11
Output: 647427950

Constraints

1 <= n <= 1000
1 <= k <= n

How to solve Number of Ways to Rearrange Sticks With K Sticks Visible

Condition on the longest stick. Placed first it is visible and the remaining n - 1 sticks must show k - 1; placed in any of the other n - 1 positions it is never visible and the remaining sticks must still show k. That gives dp[i][j] = dp[i-1][j-1] + (i-1) · dp[i-1][j].

Approach

Set dp[0][0] = 1.
Roll forward one row at a time: next[j] = dp[j-1] + (i-1) · dp[j], modulo 10⁹ + 7.
Return dp[n][k].

Why it works

Conditioning on the longest stick rather than the first position is what makes the recurrence clean: the longest stick is always visible when first, and always hidden otherwise, so the two branches are exhaustive and disjoint with no case analysis on the other sticks. These are the unsigned Stirling numbers of the first kind, which is why the row-rolling form is both natural and O(n · k).

Complexity

Time — O(n · k)
Space — O(k)

Pitfalls

The multiplier is i - 1, the number of non-first positions, not i.
dp[0][0] = 1 seeds the recurrence; every other entry of row 0 is 0.
j cannot exceed i — you cannot see more sticks than there are.

Reference solution

Python

def rearrangeSticks(n: int, k: int) -> int:
    MOD = 10**9 + 7
    dp = [0] * (k + 1)
    dp[0] = 1
    for i in range(1, n + 1):
        nxt = [0] * (k + 1)
        for j in range(1, min(k, i) + 1):
            nxt[j] = (dp[j - 1] + dp[j] * (i - 1)) % MOD
        dp = nxt
    return dp[k]

JavaScript

var rearrangeSticks = function(n, k) {
    var MOD = 1000000007, j;
    var dp = [];
    for (j = 0; j <= k; j++) dp.push(0);
    dp[0] = 1;
    for (var i = 1; i <= n; i++) {
        var next = [];
        for (j = 0; j <= k; j++) next.push(0);
        for (j = 1; j <= k && j <= i; j++) {
            next[j] = (dp[j - 1] + dp[j] * (i - 1)) % MOD;
        }
        dp = next;
    }
    return dp[k];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 213 math problems · the whole catalogue