# Number of Ways to Rearrange Sticks With K Sticks Visible
**Difficulty:** HARD
[External](https://leetcode.com/problems/number-of-ways-to-rearrange-sticks-with-k-sticks-visible)
Canonical: https://scaleengineer.com/dsa/problems/number-of-ways-to-rearrange-sticks-with-k-sticks-visible
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics)
---
## Problem
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.

* For example, if the sticks are arranged `[1,3,2,5,4]`, then the sticks with lengths `1`, `3`, and `5` are visible from the left.

Given `n` and `k`, return _the **number** of such arrangements_. Since the answer may be large, return it **modulo** `109 + 7`.

**Example 1:**

**Input:** n = 3, k = 2
**Output:** 3
**Explanation:** [1,3,2], [2,3,1], and [2,1,3] are the only arrangements such that exactly 2 sticks are visible.
The visible sticks are underlined.

**Example 2:**

**Input:** n = 5, k = 5
**Output:** 1
**Explanation:** [1,2,3,4,5] is the only arrangement such that all 5 sticks are visible.
The visible sticks are underlined.

**Example 3:**

**Input:** n = 20, k = 11
**Output:** 647427950
**Explanation:** There are 647427950 (mod 109 + 7) ways to rearrange the sticks such that exactly 11 sticks are visible.

**Constraints:**

* `1 <= n <= 1000`
* `1 <= k <= n`

# Approaches
## Top-Down DP with Memoization
This approach is based on a dynamic programming formulation of the problem. We define a function, say `dp(i, j)`, which represents the number of ways to arrange `i` sticks to have exactly `j` visible sticks. We can derive a recurrence relation for `dp(i, j)` and solve it using recursion with memoization to store and reuse the results of subproblems.
**Time:** O(n * k) because each state `(i, j)` for `1 <= i <= n` and `1 <= j <= k` is computed exactly once. · **Space:** O(n * k) for the memoization table, plus O(n + k) for the recursion stack depth.
**Pros:** Intuitive and straightforward to implement directly from the recurrence relation.; The logic closely follows the combinatorial argument.
**Cons:** Can lead to a `StackOverflowError` for large `n` and `k` if the recursion depth limit is exceeded, although modern JVMs often handle this for the given constraints.; Slightly higher constant factor overhead compared to the iterative bottom-up approach due to function call stacks.
### Explanation
The problem is equivalent to finding the unsigned Stirling numbers of the first kind, `c(n, k)`, which count the number of permutations of `n` elements with `k` disjoint cycles. The recurrence relation for these numbers is `c(n, k) = c(n-1, k-1) + (n-1) * c(n-1, k)`.

Let's derive this in the context of our stick problem. Let `dp(i, j)` be the number of ways to arrange `i` sticks (lengths 1 to `i`) with `j` visible. Consider adding the smallest stick (length 1) to an arrangement of `i-1` sticks (lengths 2 to `i`). The arrangement of sticks `{2, ..., i}` is structurally identical to an arrangement of `{1, ..., i-1}`.

1.  **Create a new visible stick**: We can start with an arrangement of `i-1` sticks having `j-1` visible sticks. To increase the visible count to `j`, we must place stick 1 in a position where it becomes visible. This is only possible by placing it at the very beginning. Since stick 1 is the shortest, it doesn't block any other sticks to its right from being visible among themselves. This contributes `dp(i-1, j-1)` ways.

2.  **Keep the number of visible sticks the same**: We can start with an arrangement of `i-1` sticks that already has `j` visible sticks. We then insert stick 1 in a way that it does *not* become visible. This can be done by placing it in any position other than the first one. There are `i-1` such positions (after each of the `i-1` existing sticks). This contributes `(i-1) * dp(i-1, j)` ways.

Combining these two cases gives the recurrence: `dp(i, j) = dp(i-1, j-1) + (i-1) * dp(i-1, j)`. We implement this using a recursive function and a 2D array for memoization to store results and avoid re-computation.

```java
class Solution {
    private int MOD = 1_000_000_007;
    private long[][] memo;

    public int rearrangeSticks(int n, int k) {
        memo = new long[n + 1][k + 1];
        for (long[] row : memo) {
            java.util.Arrays.fill(row, -1);
        }
        return (int) solve(n, k);
    }

    private long solve(int n, int k) {
        if (k < 0 || k > n) {
            return 0;
        }
        if (n == 0 && k == 0) {
            return 1;
        }
        if (n <= 0 || k <= 0) {
            return 0;
        }
        if (memo[n][k] != -1) {
            return memo[n][k];
        }

        long ans = (solve(n - 1, k - 1) + (long)(n - 1) * solve(n - 1, k)) % MOD;
        memo[n][k] = ans;
        return ans;
    }
}
```
### Algorithm
- Define a recursive function `solve(n, k)` that computes the number of arrangements for `n` sticks and `k` visible ones.
- The recurrence relation is `solve(n, k) = solve(n-1, k-1) + (n-1) * solve(n-1, k)`.
- Use a 2D array `memo` for memoization to store the results of `solve(i, j)` to avoid redundant computations.
- Base Cases:
  - If `k == 0` or `k > n`, there are no valid arrangements, so return 0.
  - If `n == k`, there is only one arrangement (`[1, 2, ..., n]`), so return 1.
- The main function initializes the memoization table with a sentinel value (e.g., -1) and calls `solve(n, k)`.

## Bottom-Up Dynamic Programming
This approach uses an iterative method to solve the same recurrence relation, building the solution from the bottom up. It avoids recursion and its associated overhead by systematically filling a 2D DP table.
**Time:** O(n * k) due to the nested loops iterating through all states. · **Space:** O(n * k) to store the 2D DP table.
**Pros:** Avoids recursion overhead and the risk of stack overflow.; Often slightly faster in practice than the memoized recursive version due to better cache locality and no function call overhead.
**Cons:** Uses O(n * k) space, which can be substantial for the given constraints (e.g., 1000x1000 table).
### Explanation
Instead of using recursion, we can build the solution iteratively. We use a 2D array, `dp[i][j]`, to store the number of ways to arrange `i` sticks with `j` visible. We fill this table starting from the base cases and use previously computed values to find the solution for larger subproblems.

The state transition is the same as in the top-down approach: `dp[i][j] = dp[i-1][j-1] + (i-1) * dp[i-1][j]`. We start with the base case `dp[0][0] = 1`. Then, we loop through the number of sticks `i` from 1 to `n`, and for each `i`, we loop through the number of visible sticks `j` from 1 up to `k`. This ensures that when we compute `dp[i][j]`, the required values `dp[i-1][j-1]` and `dp[i-1][j]` have already been computed.

```java
class Solution {
    public int rearrangeSticks(int n, int k) {
        int MOD = 1_000_000_007;
        long[][] dp = new long[n + 1][k + 1];
        dp[0][0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                long term1 = dp[i - 1][j - 1];
                long term2 = ((long)(i - 1) * dp[i - 1][j]) % MOD;
                dp[i][j] = (term1 + term2) % MOD;
            }
        }
        return (int) dp[n][k];
    }
}
```
### Algorithm
- Create a 2D array `dp` of size `(n+1) x (k+1)`.
- Initialize the base case `dp[0][0] = 1`, representing one way (the empty arrangement) for 0 sticks and 0 visible.
- Iterate `i` from 1 to `n` (for the number of sticks).
- Inside this loop, iterate `j` from 1 to `min(i, k)` (for the number of visible sticks).
- Fill the table using the recurrence: `dp[i][j] = (dp[i-1][j-1] + (long)(i-1) * dp[i-1][j]) % MOD`.
- The final answer is the value stored in `dp[n][k]`.

## Space-Optimized Bottom-Up DP
This is an optimization of the bottom-up DP approach. We observe that to compute the values for `i` sticks (row `i` in the DP table), we only need the values from `i-1` sticks (row `i-1`). This dependency allows us to reduce the space complexity from O(n*k) to O(k) by using only a single 1D array.
**Time:** O(n * k), as the nested loop structure is preserved. · **Space:** O(k) for the 1D DP array.
**Pros:** Highly efficient in terms of space, using only O(k) memory.; Maintains the O(n * k) time complexity, making it the most optimal practical solution for the given constraints.
**Cons:** The logic for the in-place update (iterating `j` backwards) can be slightly less intuitive than using a 2D array.
### Explanation
The recurrence `dp[i][j] = dp[i-1][j-1] + (i-1) * dp[i-1][j]` shows that the calculation for row `i` only depends on the values from the immediately preceding row `i-1`. This means we don't need to store the entire 2D table. We can use a single 1D array, say `dp` of size `k+1`, to store the values for the current row being computed.

To update the array in-place, we must be careful. The update rule `dp[j] = dp[j-1] + (i-1) * dp[j]` requires `dp[j-1]` from the previous row. If we iterate `j` from 1 to `k`, we would overwrite `dp[j-1]` with its new value for row `i` before using it to compute the new `dp[j]`. To solve this, we iterate `j` from `k` down to 1. This way, when we compute the new `dp[j]`, the value `dp[j-1]` is still from the previous row `i-1`, as required.

```java
class Solution {
    public int rearrangeSticks(int n, int k) {
        int MOD = 1_000_000_007;
        long[] dp = new long[k + 1];
        dp[0] = 1; // Base case: c(0, 0) = 1

        for (int i = 1; i <= n; i++) {
            // Iterate j from k down to 1 to use previous row's values correctly
            for (int j = Math.min(i, k); j >= 1; j--) {
                // dp[j] on RHS is c(i-1, j)
                // dp[j-1] on RHS is c(i-1, j-1)
                dp[j] = (dp[j - 1] + (long)(i - 1) * dp[j]) % MOD;
            }
            // For any i > 0, c(i, 0) = 0, as at least one stick is always visible.
            dp[0] = 0;
        }
        return (int) dp[k];
    }
}
```
### Algorithm
- Create a 1D array `dp` of size `(k+1)`.
- Initialize `dp[0] = 1` for the base case `c(0, 0) = 1`.
- Iterate `i` from 1 to `n` (representing the number of sticks).
- In an inner loop, iterate `j` from `min(i, k)` **down to** 1. This reverse iteration is crucial for the in-place update.
- Update `dp[j]` using the formula: `dp[j] = (dp[j-1] + (long)(i-1) * dp[j]) % MOD`. Here, `dp[j]` on the right side is the value from the `i-1` iteration, and `dp[j-1]` is also from the `i-1` iteration.
- After the inner loop, set `dp[0] = 0` because for `i > 0`, it's impossible to have 0 visible sticks.
- The final answer is `dp[k]`.

# Solutions
### Java

```java
class Solution {
public
  int rearrangeSticks(int n, int k) {
    final int mod = (int)1 e9 + 7;
    int[][] f = new int[n + 1][k + 1];
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= k; ++j) {
        f[i][j] = (int)((f[i - 1][j - 1] + f[i - 1][j] * (long)(i - 1)) % mod);
      }
    }
    return f[n][k];
  }
}

```

### CPP

```cpp
class Solution { public: int rearrangeSticks ( int n , int k ) { const int mod = 1e9 + 7 ; int f [ n + 1 ][ k + 1 ]; memset ( f , 0 , sizeof ( f )); f [ 0 ][ 0 ] = 1 ; for ( int i = 1 ; i <= n ; ++ i ) { for ( int j = 1 ; j <= k ; ++ j ) { f [ i ][ j ] = ( f [ i - 1 ][ j - 1 ] + ( i - 1LL ) * f [ i - 1 ][ j ]) % mod ; } } return f [ n ][ k ]; } };
```

### Python

```python
class Solution : def rearrangeSticks ( self , n : int , k : int ) -> int : mod = 10 ** 9 + 7 f = [[ 0 ] * ( k + 1 ) for _ in range ( n + 1 )] f [ 0 ][ 0 ] = 1 for i in range ( 1 , n + 1 ): for j in range ( 1 , k + 1 ): f [ i ][ j ] = ( f [ i - 1 ][ j - 1 ] + f [ i - 1 ][ j ] * ( i - 1 )) % mod return f [ n ][ k ]
```