Scale Engineer

Number of Ways to Rearrange Sticks With K Sticks Visible

Hard
#1705Time: O(n * k) because each state `(i, j)` for `1 <= i <= n` and `1 <= j <= k` is computed exactly once.Space: O(n * k) for the memoization table, plus O(n + k) for the recursion stack depth.
Patterns
MathDynamic ProgrammingCombinatorics

Prompt

There are n uniquely-sized sticks whose lengths are integers from 1 to n. You want to arrange the sticks such that exactly k sticks are visible from the left. A stick is visible from the left if there are no longer sticks to the left of it.

  • For example, if the sticks are arranged [1,3,2,5,4], then the sticks with lengths 1, 3, and 5 are visible from the left.

Given n and k, return the number of such arrangements. Since the answer may be large, return it modulo 109 + 7.

 

Example 1:

Input: n = 3, k = 2
Output: 3
Explanation: [1,3,2], [2,3,1], and [2,1,3] are the only arrangements such that exactly 2 sticks are visible.
The visible sticks are underlined.

Example 2:

Input: n = 5, k = 5
Output: 1
Explanation: [1,2,3,4,5] is the only arrangement such that all 5 sticks are visible.
The visible sticks are underlined.

Example 3:

Input: n = 20, k = 11
Output: 647427950
Explanation: There are 647427950 (mod 109 + 7) ways to rearrange the sticks such that exactly 11 sticks are visible.

 

Constraints:

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach is based on a dynamic programming formulation of the problem. We define a function, say dp(i, j), which represents the number of ways to arrange i sticks to have exactly j visible sticks. We can derive a recurrence relation for dp(i, j) and solve it using recursion with memoization to store and reuse the results of subproblems.

Algorithm

  • Define a recursive function solve(n, k) that computes the number of arrangements for n sticks and k visible ones.
  • The recurrence relation is solve(n, k) = solve(n-1, k-1) + (n-1) * solve(n-1, k).
  • Use a 2D array memo for memoization to store the results of solve(i, j) to avoid redundant computations.
  • Base Cases:
    • If k == 0 or k > n, there are no valid arrangements, so return 0.
    • If n == k, there is only one arrangement ([1, 2, ..., n]), so return 1.
  • The main function initializes the memoization table with a sentinel value (e.g., -1) and calls solve(n, k).

Walkthrough

The problem is equivalent to finding the unsigned Stirling numbers of the first kind, c(n, k), which count the number of permutations of n elements with k disjoint cycles. The recurrence relation for these numbers is c(n, k) = c(n-1, k-1) + (n-1) * c(n-1, k).

Let's derive this in the context of our stick problem. Let dp(i, j) be the number of ways to arrange i sticks (lengths 1 to i) with j visible. Consider adding the smallest stick (length 1) to an arrangement of i-1 sticks (lengths 2 to i). The arrangement of sticks {2, ..., i} is structurally identical to an arrangement of {1, ..., i-1}.

  1. Create a new visible stick: We can start with an arrangement of i-1 sticks having j-1 visible sticks. To increase the visible count to j, we must place stick 1 in a position where it becomes visible. This is only possible by placing it at the very beginning. Since stick 1 is the shortest, it doesn't block any other sticks to its right from being visible among themselves. This contributes dp(i-1, j-1) ways.

  2. Keep the number of visible sticks the same: We can start with an arrangement of i-1 sticks that already has j visible sticks. We then insert stick 1 in a way that it does not become visible. This can be done by placing it in any position other than the first one. There are i-1 such positions (after each of the i-1 existing sticks). This contributes (i-1) * dp(i-1, j) ways.

Combining these two cases gives the recurrence: dp(i, j) = dp(i-1, j-1) + (i-1) * dp(i-1, j). We implement this using a recursive function and a 2D array for memoization to store results and avoid re-computation.

class Solution {    private int MOD = 1_000_000_007;    private long[][] memo;     public int rearrangeSticks(int n, int k) {        memo = new long[n + 1][k + 1];        for (long[] row : memo) {            java.util.Arrays.fill(row, -1);        }        return (int) solve(n, k);    }     private long solve(int n, int k) {        if (k < 0 || k > n) {            return 0;        }        if (n == 0 && k == 0) {            return 1;        }        if (n <= 0 || k <= 0) {            return 0;        }        if (memo[n][k] != -1) {            return memo[n][k];        }         long ans = (solve(n - 1, k - 1) + (long)(n - 1) * solve(n - 1, k)) % MOD;        memo[n][k] = ans;        return ans;    }}

Complexity

Time

O(n * k) because each state `(i, j)` for `1 <= i <= n` and `1 <= j <= k` is computed exactly once.

Space

O(n * k) for the memoization table, plus O(n + k) for the recursion stack depth.

Trade-offs

Pros

  • Intuitive and straightforward to implement directly from the recurrence relation.

  • The logic closely follows the combinatorial argument.

Cons

  • Can lead to a StackOverflowError for large n and k if the recursion depth limit is exceeded, although modern JVMs often handle this for the given constraints.

  • Slightly higher constant factor overhead compared to the iterative bottom-up approach due to function call stacks.

Solutions

class Solution {public  int rearrangeSticks(int n, int k) {    final int mod = (int)1 e9 + 7;    int[][] f = new int[n + 1][k + 1];    f[0][0] = 1;    for (int i = 1; i <= n; ++i) {      for (int j = 1; j <= k; ++j) {        f[i][j] = (int)((f[i - 1][j - 1] + f[i - 1][j] * (long)(i - 1)) % mod);      }    }    return f[n][k];  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem