Number of ways to rearrange sticks with k sticks visible

Math Dynamic Programming Combinatorics

60.5% acceptance

Feb 25, 2026

755

There are n uniquely-sized sticks whose lengths are integers from 1 to n. You want to arrange the sticks such that exactly k sticks are visible from the left. A stick is visible from the left if there are no longer sticks to the left of it. Given n and k, return the number of such arrangements modulo 10^9 + 7.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn rearrange_sticks(n: i32, k: i32) -> i32 {
    // This equals the unsigned Stirling numbers of the first kind s(n, k).
    // Recurrence: s(n, k) = s(n-1, k-1) + (n-1) * s(n-1, k)
    const MOD: u64 = 1_000_000_007;
    let (n, k) = (n as usize, k as usize);
    let mut dp = vec![0u64; k + 1];
    dp[0] = 1;
    for i in 1..=n {
      let mut new_dp = vec![0u64; k + 1];
      for j in 1..=k.min(i) {
        new_dp[j] = (dp[j - 1] + (i as u64 - 1) * dp[j]) % MOD;
      }
      dp = new_dp;
    }
    dp[k] as i32
  }
}