Number of Ways to Rearrange Sticks With K Sticks Visible

Hard
1096.

Number of Ways to Rearrange Sticks With K Sticks Visible

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.

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 <= 1000
  • 1 <= k <= n
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var rearrangeSticks = function(n, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 1000
  • 1 <= k <= n

Hints for Number of Ways to Rearrange Sticks With K Sticks Visible

  1. 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.

  2. Hint 2

    If it is anywhere else, it hides nothing that was already visible — and there are n - 1 positions for it.

  3. 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

  1. Set dp[0][0] = 1.
  2. Roll forward one row at a time: next[j] = dp[j-1] + (i-1) · dp[j], modulo 10⁹ + 7.
  3. 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, not i.
  • dp[0][0] = 1 seeds the recurrence; every other entry of row 0 is 0.
  • j cannot exceed i — 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