Number of Ways to Rearrange Sticks With K Sticks Visible Solution
Number of Ways to Rearrange Sticks With K Sticks Visible solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Number of Ways to Rearrange Sticks With K Sticks Visible is a hard coding problem on dynamic programming, math and combinatorics, asked in Amazon, Google and Meta interviews.
- Difficulty: Hard
- Topics: Dynamic Programming, Math, Combinatorics
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are n sticks of distinct lengths 1 through n. Arrange them in a row; a stick is visible from the left when every stick before it is shorter.
Return the number of arrangements in which exactly k sticks are visible, modulo 10⁹ + 7.
Example 1
Input: n = 3, k = 2
Output: 3
Explanation: `[1,3,2]`, `[2,3,1]` and `[2,1,3]`.
Example 2
Input: n = 5, k = 5
Output: 1
Explanation: Only the fully sorted arrangement shows all five.
Example 3
Input: n = 20, k = 11
Output: 647427950
Constraints
1 <= n <= 10001 <= k <= n
Hints for Number of Ways to Rearrange Sticks With K Sticks Visible
Hint 1
Think about where the longest stick goes. If it is first, it is visible and the rest is a smaller instance needing
k - 1.Hint 2
If it is anywhere else, it hides nothing that was already visible — and there are
n - 1positions for it.Hint 3
dp[i][j] = dp[i-1][j-1] + (i-1) · dp[i-1][j]— the unsigned Stirling numbers of the first kind.
How to solve Number of Ways to Rearrange Sticks With K Sticks Visible
Condition on the longest stick. Placed first it is visible and the remaining n - 1 sticks must show k - 1; placed in any of the other n - 1 positions it is never visible and the remaining sticks must still show k. That gives dp[i][j] = dp[i-1][j-1] + (i-1) · dp[i-1][j].
Approach
- Set
dp[0][0] = 1. - Roll forward one row at a time:
next[j] = dp[j-1] + (i-1) · dp[j], modulo 10⁹ + 7. - Return
dp[n][k].
Why it works
Conditioning on the longest stick rather than the first position is what makes the recurrence clean: the longest stick is always visible when first, and always hidden otherwise, so the two branches are exhaustive and disjoint with no case analysis on the other sticks. These are the unsigned Stirling numbers of the first kind, which is why the row-rolling form is both natural and O(n · k).
Complexity
- Time —
O(n · k) - Space —
O(k)
Pitfalls
- The multiplier is
i - 1, the number of non-first positions, noti. dp[0][0] = 1seeds the recurrence; every other entry of row 0 is 0.jcannot exceedi— you cannot see more sticks than there are.
Reference solution
Python
def rearrangeSticks(n: int, k: int) -> int:
MOD = 10**9 + 7
dp = [0] * (k + 1)
dp[0] = 1
for i in range(1, n + 1):
nxt = [0] * (k + 1)
for j in range(1, min(k, i) + 1):
nxt[j] = (dp[j - 1] + dp[j] * (i - 1)) % MOD
dp = nxt
return dp[k]Java
public static int rearrangeSticks(int n, int k) {
final long MOD = 1000000007L;
long[] dp = new long[k + 1];
dp[0] = 1;
for (int i = 1; i <= n; i++) {
long[] next = new long[k + 1];
for (int j = 1; j <= k && j <= i; j++) {
next[j] = (dp[j - 1] + dp[j] * (i - 1)) % MOD;
}
dp = next;
}
return (int) dp[k];
}C++
int rearrangeSticks(int n, int k) {
const long long MOD = 1000000007LL;
vector<long long> dp(k + 1, 0);
dp[0] = 1;
for (int i = 1; i <= n; i++) {
vector<long long> next(k + 1, 0);
for (int j = 1; j <= k && j <= i; j++) {
next[j] = (dp[j - 1] + dp[j] * (i - 1)) % MOD;
}
dp = next;
}
return (int) dp[k];
}JavaScript
var rearrangeSticks = function(n, k) {
var MOD = 1000000007, j;
var dp = [];
for (j = 0; j <= k; j++) dp.push(0);
dp[0] = 1;
for (var i = 1; i <= n; i++) {
var next = [];
for (j = 0; j <= k; j++) next.push(0);
for (j = 1; j <= k && j <= i; j++) {
next[j] = (dp[j - 1] + dp[j] * (i - 1)) % MOD;
}
dp = next;
}
return dp[k];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming