LeetCode 1866 - Number of Ways to Rearrange Sticks With K Sticks Visible

LeetCode Problem 1866

Difficulty: 🔴 Hard
Topics: Math, Dynamic Programming, Combinatorics

Solution

Problem Understanding

The problem gives us n sticks with unique lengths from 1 to n. We must arrange these sticks in some order so that exactly k sticks are visible when looking from the left side.

A stick is visible if every stick before it is shorter. In other words, a stick is visible if it creates a new maximum height while scanning from left to right.

For example, in the arrangement [1,3,2,5,4]:

• 1 is visible because nothing is before it.
• 3 is visible because it is taller than 1.
• 2 is not visible because 3 blocks it.
• 5 is visible because it is taller than everything before it.
• 4 is not visible because 5 blocks it.

So there are exactly 3 visible sticks.

The task is to count how many permutations of the numbers 1 through n produce exactly k visible sticks. Since the number of permutations grows extremely quickly, we return the answer modulo 10^9 + 7.

The constraints are important:

• 1 <= n <= 1000
• 1 <= k <= n

A brute force solution would require checking all n! permutations, which becomes impossible even for moderate values of n. For example:

• 10! = 3,628,800
• 15! is already over one trillion
• 1000! is astronomically large

This immediately suggests that we need a combinatorial or dynamic programming solution.

Several edge cases are important:

• k = 1, only one stick is visible. This happens when the tallest stick appears first.
• k = n, every stick is visible. This only happens when the sticks are in strictly increasing order.
• n = 1, there is only one arrangement and one visible stick.
• Large values like n = 1000, where recursion without memoization or factorial enumeration would fail.

Approaches

Brute Force Approach

The most straightforward idea is to generate every permutation of the sticks and count how many visible sticks each arrangement produces.

For every permutation:

1. Scan from left to right.
2. Track the tallest stick seen so far.
3. Whenever a taller stick appears, increment the visible count.
4. If the visible count equals k, increment the answer.

This approach is correct because it explicitly checks every possible arrangement.

However, it is far too slow. There are n! permutations, and each permutation requires O(n) work to count visible sticks. The total complexity becomes O(n × n!), which is completely infeasible for n = 1000.

Key Insight

Instead of constructing full permutations directly, we can build the answer incrementally using dynamic programming.

Suppose we already know the number of valid arrangements for n - 1 sticks. How can we insert the largest stick n?

The largest stick is special because it is always visible whenever it appears.

There are two possibilities:

1. Place stick n at the front.

• It becomes visible.
• The remaining n - 1 sticks must contribute k - 1 visible sticks.
• Contribution:

dp[n-1][k-1] 2. Place stick n somewhere other than the front.

• Since n is the tallest stick, it will block visibility for everything after it.
• It does not create a new visible count beyond what already existed before it.
• There are n - 1 possible insertion positions after the first position.
• Contribution:

(n - 1) * dp[n-1][k]

This gives the recurrence:

$$dp[n][k] = dp[n-1][k-1] + (n-1) \times dp[n-1][k]$$

This recurrence is the core insight that makes the problem tractable.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × n!)	O(n)	Enumerates every permutation
Optimal Dynamic Programming	O(n × k)	O(n × k)	Uses combinatorial recurrence

Algorithm Walkthrough

1. Define dp[i][j] as the number of ways to arrange i sticks such that exactly j sticks are visible from the left.
2. Initialize the base case:

• dp[1][1] = 1
• With one stick, there is exactly one arrangement and one visible stick.

3. Iterate from i = 2 to n.

• We compute all answers involving i sticks using previously computed states.

4. For each j from 1 to min(i, k):

• Consider where to place the largest stick i.

5. Case 1, place stick i at the beginning:

• The largest stick becomes visible immediately.
• The remaining i - 1 sticks must contribute j - 1 visible sticks.
• Add:

dp[i-1][j-1] 6. Case 2, place stick i somewhere after the first position:

• There are i - 1 choices.
• Since stick i is tallest, it does not increase the visible count when inserted later.
• Add:

(i - 1) * dp[i-1][j] 7. Combine both contributions:

$$dp[i][j] = dp[i-1][j-1] + (i-1)\times dp[i-1][j]$$ 8. Apply modulo 10^9 + 7 after every update to avoid overflow. 9. Return dp[n][k].

Why it works

The recurrence partitions all valid arrangements into two disjoint categories based on the position of the largest stick. Every valid permutation belongs to exactly one of these categories, and both categories preserve the visibility count in predictable ways. Since the recurrence exhausts all possibilities without overlap, the DP computes the exact number of valid arrangements.

Python Solution

class Solution:
    def rearrangeSticks(self, n: int, k: int) -> int:
        MOD = 10**9 + 7

        dp = [[0] * (k + 1) for _ in range(n + 1)]
        dp[1][1] = 1

        for sticks in range(2, n + 1):
            for visible in range(1, min(sticks, k) + 1):
                place_front = dp[sticks - 1][visible - 1]

                place_elsewhere = (
                    (sticks - 1) * dp[sticks - 1][visible]
                ) % MOD

                dp[sticks][visible] = (
                    place_front + place_elsewhere
                ) % MOD

        return dp[n][k]

The implementation directly mirrors the recurrence relation.

The dp table stores the number of valid arrangements for every combination of stick count and visible count.

The outer loop iterates over the number of sticks currently being considered. The inner loop computes all possible visible counts for that stick count.

For every state:

• place_front corresponds to placing the largest stick first.
• place_elsewhere corresponds to inserting the largest stick into one of the remaining positions.

The modulo operation is applied after multiplication and addition to ensure values remain within bounds.

Finally, dp[n][k] contains the desired answer.

Go Solution

func rearrangeSticks(n int, k int) int {
    const MOD int = 1_000_000_007

    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, k+1)
    }

    dp[1][1] = 1

    for sticks := 2; sticks <= n; sticks++ {
        limit := k
        if sticks < k {
            limit = sticks
        }

        for visible := 1; visible <= limit; visible++ {
            placeFront := dp[sticks-1][visible-1]

            placeElsewhere := int(
                (int64(sticks-1) * int64(dp[sticks-1][visible])) % int64(MOD),
            )

            dp[sticks][visible] =
                (placeFront + placeElsewhere) % MOD
        }
    }

    return dp[n][k]
}

The Go implementation follows the same recurrence and DP structure as the Python version.

The main Go-specific consideration is integer overflow. Multiplication between (sticks - 1) and dp[sticks-1][visible] can exceed 32-bit integer limits, so the multiplication is performed using int64 before converting back to int.

Slices are used to construct the two-dimensional DP table dynamically.

Worked Examples

Example 1

Input:

n = 3, k = 2

We build the DP table step by step.

Initial state:

i	j	dp[i][j]
1	1	1

For i = 2:

j = 1

$$dp[2][1] = dp[1][0] + 1 \times dp[1][1]$$

$$= 0 + 1 \times 1 = 1$$

j = 2

$$dp[2][2] = dp[1][1] + 1 \times dp[1][2]$$

$$= 1 + 0 = 1$$

Current table:

i	j	dp[i][j]
2	1	1
2	2	1

For i = 3:

j = 1

$$dp[3][1] = dp[2][0] + 2 \times dp[2][1]$$

$$= 0 + 2 \times 1 = 2$$

j = 2

$$dp[3][2] = dp[2][1] + 2 \times dp[2][2]$$

$$= 1 + 2 \times 1 = 3$$

j = 3

$$dp[3][3] = dp[2][2] + 2 \times dp[2][3]$$

$$= 1 + 0 = 1$$

Final answer:

dp[3][2] = 3

Example 2

Input:

n = 5, k = 5

To have all 5 sticks visible, every stick must be taller than all previous sticks.

That only happens in strictly increasing order:

[1,2,3,4,5]

The DP recurrence eventually produces:

i	j	dp[i][j]
5	5	1

Final answer:

1

Example 3

Input:

n = 20, k = 11

The DP fills states incrementally up to dp[20][11].

After all computations:

dp[20][11] = 647427950

This value is already modulo 10^9 + 7.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n × k)	Each DP state is computed once
Space	O(n × k)	DP table stores all states

The DP table contains (n + 1) × (k + 1) states. Every state requires constant work using the recurrence relation, so the total runtime is O(n × k).

The space complexity is also O(n × k) because we store the entire table. This is efficient enough for n <= 1000.

Test Cases

sol = Solution()

# Provided examples
assert sol.rearrangeSticks(3, 2) == 3  # Example 1
assert sol.rearrangeSticks(5, 5) == 1  # Strictly increasing order
assert sol.rearrangeSticks(20, 11) == 647427950  # Large example

# Smallest input
assert sol.rearrangeSticks(1, 1) == 1  # Single stick

# Only one visible stick
assert sol.rearrangeSticks(2, 1) == 1  # [2,1]
assert sol.rearrangeSticks(3, 1) == 2  # [3,1,2], [3,2,1]

# All sticks visible
assert sol.rearrangeSticks(2, 2) == 1  # [1,2]
assert sol.rearrangeSticks(3, 3) == 1  # [1,2,3]

# Intermediate values
assert sol.rearrangeSticks(4, 2) == 11  # Known DP result
assert sol.rearrangeSticks(4, 3) == 6   # Known DP result

# Larger boundary-style checks
assert sol.rearrangeSticks(10, 1) == 362880  # (10-1)!
assert sol.rearrangeSticks(10, 10) == 1      # Increasing order only

# Validity checks
assert sol.rearrangeSticks(6, 2) > 0  # General nontrivial case
assert sol.rearrangeSticks(8, 4) > 0  # Medium-sized state

Test	Why
rearrangeSticks(3, 2)	Verifies sample input
rearrangeSticks(5, 5)	Tests all-visible scenario
rearrangeSticks(20, 11)	Tests large DP computation
rearrangeSticks(1, 1)	Smallest valid input
rearrangeSticks(3, 1)	Tests single visible stick behavior
rearrangeSticks(3, 3)	Tests strictly increasing arrangement
rearrangeSticks(4, 2)	Verifies intermediate DP transitions
rearrangeSticks(10, 1)	Confirms factorial-related pattern
rearrangeSticks(8, 4)	General medium-sized correctness case

Edge Cases

One important edge case is k = 1. In this scenario, only the first stick can be visible. The tallest stick must therefore appear first, otherwise another stick would become visible before it. A buggy implementation might incorrectly count additional permutations. The DP handles this naturally through the recurrence, and the resulting values match (n - 1)!.

Another critical edge case is k = n. Every stick must be visible, which means the arrangement must be strictly increasing. There is exactly one valid arrangement. The recurrence correctly preserves this property because every new largest stick must be inserted at the front-visible position.

The smallest input, n = 1 and k = 1, is also important. Without a proper base case, the recurrence would reference invalid states and produce zero instead of one. Initializing dp[1][1] = 1 ensures the DP builds correctly from the smallest valid configuration.

A subtle edge case involves modulo arithmetic. Intermediate multiplication values can become extremely large, especially near n = 1000. Without taking modulo after multiplication and addition, integer overflow could occur in languages like Go. The implementation avoids this by applying modulo consistently during every transition.