#1866

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Number of Ways to Rearrange Sticks With K Sticks Visible

Calculate the number of arrangements of n uniquely-sized sticks so exactly k sticks are visible using dynamic programming.

math dynamic programming combinatorics

Problem Statement

You are given n sticks with unique lengths numbered 1 to n. A stick is visible from the left if all sticks before it are shorter. Your task is to count arrangements where exactly k sticks are visible from the left.

Return the total number of valid arrangements modulo 10^9 + 7. For example, with n = 3 and k = 2, the arrangements [1,3,2], [2,3,1], and [2,1,3] satisfy the visibility requirement.

Examples

Example 1

Input: n = 3, k = 2

Output: 3

[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

[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

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

Solution Approach

Define DP state and base case

Let dp[n][k] represent the number of ways to arrange n sticks so that exactly k are visible. Base case is dp[0][0] = 1. This aligns with state transition DP, allowing incremental computation.

State transition formulation

For each new stick, either it becomes the new leftmost visible stick, increasing k, or it is hidden, keeping k unchanged. The recurrence is dp[n][k] = dp[n-1][k-1] + (n-1)*dp[n-1][k], reflecting combinatorial placement choices.

Iterative computation and modulo handling

Fill the DP table iteratively from 1 to n, ensuring all operations use modulo 10^9 + 7 to prevent overflow. This ensures accurate counts for large n while maintaining efficient O(n*k) time complexity.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n k) due to iterating over all DP states. Space complexity is O(n k) for the DP table, which can be reduced to O(k) using rolling arrays. Each state only depends on the previous row.

What Interviewers Usually Probe

Focus on defining a clear DP state that represents visible sticks.
Watch for off-by-one errors in indexing k or n during state transitions.
Check modulo operations to prevent integer overflow on large inputs.

Common Pitfalls or Variants

Common pitfalls

Failing to account for sticks that are hidden, which affects the recurrence.
Incorrect base case initialization causing invalid results for small n or k.
Mixing up the visible and hidden stick counts in the DP formula.

Follow-up variants

Count arrangements with exactly k visible sticks from the right instead of the left.
Compute arrangements for sticks with duplicate lengths while maintaining visibility counts.
Generalize the problem to find arrangements with at least k visible sticks.

FAQ

What is the best approach to solve Number of Ways to Rearrange Sticks With K Sticks Visible?

Use state transition dynamic programming with dp[n][k] representing arrangements with exactly k visible sticks.

How do I handle large results in this problem?

Always apply modulo 10^9 + 7 after each DP calculation to prevent integer overflow.

Can the DP solution be optimized in space?

Yes, by using a rolling array, space can be reduced from O(n*k) to O(k) since only the previous row is needed.

What are common mistakes when defining the DP recurrence?

Mixing up the counts of visible and hidden sticks or misapplying the combinatorial factor (n-1) can lead to wrong answers.

Is there a way to verify the DP approach quickly?

Test small examples such as n = 3, k = 2 or n = 5, k = 5 to ensure the DP table produces correct counts.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i][j]$ to represent the number of permutations of length $i$ in which exactly $j$ sticks can be seen. Initially, $f[0][0]=1$ and the rest $f[i][j]=0$. The answer is $f[n][k]$.

1

2

3

4

5

6

7

8

9

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]

Solution 2: Dynamic Programming (Space Optimization)

We notice that $f[i][j]$ is only related to $f[i - 1][j - 1]$ and $f[i - 1][j]$, so we can use a one-dimensional array to optimize the space complexity.

1

2

3

4

5

6

7

8

9

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]

Continue Practicing

#1916 count ways to build rooms in an ant colony #1735 count ways to make array with product #2063 vowels of all substrings