NeetCode #742LC-1866Hard2-D Dynamic Programming
← Back to All Problems#742 · #1866 · Number of Ways to Rearrange Sticks With K Sticks Visible(恰有 K 根木棍可以看到的排列数目)
📌 Problem Statement & Constraints
There are
n sticks of distinct heights 1 to n. Count the permutations in which exactly k sticks are visible when viewed from the left (a stick is visible if it is taller than every stick to its left). Return the count modulo 1e9+7. Constraints: 1 <= n <= 1000, 1 <= k <= n.💡 Core Algorithmic Approaches
- Insert the tallest stick last, into a permutation of the other
n - 1sticks. - If the tallest stick is placed first, it is visible and adds one to the count: this gives
dp[n-1][k-1]. - If it is placed anywhere else, it is hidden and does not change visibility; there are
n - 1such insertion positions: this gives(n-1) * dp[n-1][k]. - So
dp[n][k] = dp[n-1][k-1] + (n-1) * dp[n-1][k], the unsigned Stirling numbers of the first kind.
💻 Benchmark Python3 Implementation
class Solution:
def rearrangeSticks(self, n: int, k: int) -> int:
MOD = 10**9 + 7
dp = [0] * (k + 1)
dp[0] = 1 # zero sticks -> the empty arrangement
for i in range(1, n + 1):
nxt = [0] * (k + 1)
for j in range(1, min(i, k) + 1):
# tallest stick first (visible) + inserted among i-1 slots (hidden)
nxt[j] = (dp[j - 1] + (i - 1) * dp[j]) % MOD
dp = nxt
return dp[k]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n * k): each of n layers fills up to k states.
💾 Space Complexity
O(k): one rolling array.
⚠️ Interview Pitfalls & Follow-ups
- Inserting the shortest stick instead: the recurrence is cleanest with the tallest stick, because it is visible exactly when it sits first and hidden in every other slot.
- Forgetting the
(i-1)factor: the tallest stick hasi - 1non-first insertion positions, each contributing a distinct permutation. - Using a full
n x ktable: only the previous stick count is needed, so a 1-D array suffices. - Setting
dp[0] = 0: with zero sticks there is exactly one arrangement (empty), sodp[0]must start at 1; all other cells start at 0.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.