Problem Description

You are given two integers, n and k. There are n uniquely sized sticks, all standing vertically in a row. You want to rearrange the sticks in any order. After rearrangement, you look at the row from the left side, and a stick is visible if it is taller than every stick before it.

The task is to determine the number of ways to rearrange the sticks so that exactly k sticks are visible from the left. The answer can be large, so return it modulo 10^9 + 7.

Constraints:

• 1 ≤ k ≤ n ≤ 1000

• Each stick has a unique height.
• All permutations of the sticks are allowed.
• Do not reuse sticks; each stick is used once per arrangement.
• Exactly k sticks must be visible from the left after rearrangement.

Thought Process

At first glance, the problem seems to ask for all permutations of n sticks, but with the added twist that only k of them are visible from the left. A brute-force solution would be to generate all possible permutations of the sticks and count those with exactly k visible sticks. However, this approach is not feasible for large n due to the factorial growth of permutations.

Instead, we need to find a way to count valid arrangements efficiently, likely using dynamic programming. The key insight is to think recursively: if we already know the number of ways for n-1 sticks and k-1 visible sticks, can we build up to n and k? This hints at a relationship or recurrence that can be exploited for efficient computation.

Solution Approach

The problem is a classic case of dynamic programming using a recurrence relation.

Let dp[n][k] represent the number of ways to arrange n sticks such that exactly k are visible from the left.

Recurrence Relation:

• When adding the tallest stick (height = n), it must be visible (since it's taller than all previous), so we must arrange the remaining n-1 sticks such that k-1 are visible: dp[n-1][k-1].
• When the tallest stick is not at the leftmost position, it can be placed in any of the other n-1 spots. In these cases, the number of visible sticks remains k, and we arrange the remaining n-1 sticks with k visible: (n-1) * dp[n-1][k].

• dp[0][0] = 1: No sticks, no visible sticks, one way (the empty arrangement).
• dp[n][0] = 0 for n > 0: Can't have zero visible sticks with nonzero sticks.
• dp[n][k] = 0 if k > n: Can't have more visible sticks than total sticks.

1. Create a 2D DP table of size (n+1) x (k+1).
2. Initialize base cases.
3. Iteratively fill the table using the recurrence relation.
4. Return dp[n][k] % (10^9 + 7).

• Subproblems overlap: dp[n-1][k] and dp[n-1][k-1] are reused.
• Bottom-up DP avoids repeated computation and stack overflow.

Example Walkthrough

Let's walk through a small example: n = 3, k = 2.

Step 1: List all permutations of 3 sticks:
(A, B, C), (A, C, B), (B, A, C), (B, C, A), (C, A, B), (C, B, A)
Assume heights are: 1 (A), 2 (B), 3 (C)
Step 2: For each arrangement, count visible sticks from the left:

• (A, B, C): 3 visible
• (A, C, B): 2 visible
• (B, A, C): 2 visible
• (B, C, A): 2 visible
• (C, A, B): 1 visible
• (C, B, A): 1 visible

• Base: dp[1][1] = 1
• dp[2][1] = (2-1) * dp[1][1] = 1*1 = 1
• dp[2][2] = dp[1][1] = 1
• dp[3][2] = dp[2][1] + 2*dp[2][2] = 1 + 2*1 = 3

Time and Space Complexity

Brute-Force Approach:

• Time: O(n!) (Enumerate all permutations)
• Space: O(n) (Stack for recursion or permutation storage)

• Time: O(nk) (Each dp[n][k] is computed once, and there are n*k entries)
• Space: O(nk) (DP table size)

Summary

The problem asks for the number of stick arrangements with exactly k visible from the left. A brute-force solution is infeasible, but by recognizing the problem's recursive structure, we use dynamic programming with a simple recurrence. This approach is both elegant and efficient, leveraging overlapping subproblems and optimal substructure, and is a classic example of DP in combinatorics.

Code Implementation

MOD = 10 ** 9 + 7

def rearrangeSticks(n: int, k: int) -> int:
    dp = [[0] * (k + 2) for _ in range(n + 2)]
    dp[0][0] = 1
    for i in range(1, n + 1):
        for j in range(1, k + 1):
            dp[i][j] = (dp[i-1][j-1] + (i-1) * dp[i-1][j]) % MOD
    return dp[n][k]
      

const int MOD = 1e9 + 7;

class Solution {
public:
    int rearrangeSticks(int n, int k) {
        vector<vector<long long>> dp(n+2, vector<long long>(k+2, 0));
        dp[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= k; ++j) {
                dp[i][j] = (dp[i-1][j-1] + (i-1) * dp[i-1][j]) % MOD;
            }
        }
        return dp[n][k];
    }
};
      

class Solution {
    static final int MOD = 1000000007;
    public int rearrangeSticks(int n, int k) {
        long[][] dp = new long[n + 2][k + 2];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                dp[i][j] = (dp[i-1][j-1] + (i-1) * dp[i-1][j]) % MOD;
            }
        }
        return (int) dp[n][k];
    }
}
      

const MOD = 1e9 + 7;

var rearrangeSticks = function(n, k) {
    const dp = Array.from({length: n + 2}, () => Array(k + 2).fill(0));
    dp[0][0] = 1;
    for (let i = 1; i <= n; ++i) {
        for (let j = 1; j <= k; ++j) {
            dp[i][j] = (dp[i-1][j-1] + (i-1) * dp[i-1][j]) % MOD;
        }
    }
    return dp[n][k];
};