Number of Ways to Rearrange Sticks
Hard · Dynamic Programming · Math · Dynamic Programming · Combinatorics
Problem
You have n sticks with distinct lengths 1, 2, ..., n. Arrange all of them in a row.
Looking from the left, a stick is visible if every stick to its left is shorter than it. Return the number of arrangements in which exactly k sticks are visible, modulo 10^9 + 7.
Examples
Input: n = 4, k = 2 Output: 11
Eleven of the 24 orderings of lengths 1-4 show exactly two sticks from the left, for example [2,1,4,3].
Input: n = 4, k = 4 Output: 1
All four sticks are visible only in the order [1,2,3,4].
Input: n = 5, k = 1 Output: 24
Only the tallest stick is visible exactly when it comes first; the other four follow in any of 4! = 24 orders.
Constraints
- 1 <= n <= 1000
- 1 <= k <= n
Approaches
- Split at the tallest stick — time O(n² · k), space O(n · k)
Follow-up
These counts are the unsigned Stirling numbers of the first kind: arrangements of n with k visible sticks correspond to permutations with k cycles. Can you count arrangements with exactly a sticks visible from the left and b from the right?
Related problems
Start free on Cariara · Coding problems · System design studio
