⚡Flashcard Drill➔
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

  1. Insert the tallest stick last, into a permutation of the other n - 1 sticks.
  2. If the tallest stick is placed first, it is visible and adds one to the count: this gives dp[n-1][k-1].
  3. If it is placed anywhere else, it is hidden and does not change visibility; there are n - 1 such insertion positions: this gives (n-1) * dp[n-1][k].
  4. 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 has i - 1 non-first insertion positions, each contributing a distinct permutation.
  • Using a full n x k table: 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), so dp[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.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems