Number of Ways to Rearrange Sticks With K Sticks Visible solution and explanation
Google
8 more videos on this problem
Number of Ways to Rearrange Sticks With K Sticks Visible - Dynamic Programming - Leetcode 1866NeetCode · 14:53 · 17K views
LeetCode 1866. Number of Ways to Rearrange Sticks With K Sticks VisibleHappy Coding · 17:56 · 823 views
【每日一题】1866. Number of Ways to Rearrange Sticks With K Sticks Visible, 5/20/2021Huifeng Guan · 40:10 · 626 views
LeetCode Weekly Contest 241 Question 4: Number of Ways to Rearrange Sticks With K Sticks VisibleCoding Ninjas Webinars and Contest Editorials · 19:09 · 506 views
1866. Number of Ways to Rearrange Sticks With K Sticks Visible (Leetcode Hard)Programming Live with Larry · 21:53 · 498 views
Number of Ways to Rearrange Sticks With K Sticks Visible-Dynamic programming || Leetcode 1886(HARD)Code with Developers · 12:03 · 266 views
1866. Leetcode . Number of ways to rearrange sticks with K visible. Aryan · 36:11 · 163 views
1866. Number of Ways to Rearrange Sticks With K Sticks Visible Hard Leetcode Weekly Contest (IITG)Rajat's corner ; Microsoft | IITG · 14:28 · 109 views
LeetCode 1866: Number of Ways to Rearrange Sticks With K Sticks VisibleAlitaCode · 26:58 · 18 views
The problem
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 lengths1,3, and5are 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 <= 10001 <= k <= n
Approach overview
Problem Overview: You are given n sticks with distinct heights from 1 to n. When arranged in a line, a stick becomes visible from the left if it is taller than every stick before it. The task is to count how many permutations of the sticks produce exactly k visible sticks.
Approach 1: Recursive Dynamic Programming with Memoization (Time: O(n*k), Space: O(n*k))
This problem has a classic combinatorics recurrence. When placing the tallest stick among n sticks, two situations occur. If the tallest stick is placed at the front, it will definitely be visible, so the remaining n-1 sticks must produce k-1 visible sticks. If it is placed somewhere else, it will be hidden behind a taller prefix, and you have n-1 possible positions to place it while keeping the visible count unchanged. This gives the recurrence dp[n][k] = dp[n-1][k-1] + (n-1) * dp[n-1][k]. Using recursion with memoization avoids recomputing overlapping states and efficiently evaluates the count modulo 1e9+7. The technique relies heavily on ideas from dynamic programming and combinatorics.
Approach 2: Bottom-Up Dynamic Programming (Time: O(n*k), Space: O(n*k))
The recurrence can be implemented iteratively using a 2D DP table where dp[i][j] represents the number of ways to arrange i sticks so exactly j are visible. Initialize dp[1][1] = 1. For each i from 2 to n, compute values for all valid j. The transition directly follows the recurrence: placing the tallest stick at the front increases visible count, while inserting it in any of the remaining i-1 positions keeps the same visible count. This tabulation method is easier to debug and avoids recursion overhead. It also clearly shows the combinatorial structure of the problem, closely related to permutations studied in math problems.
Approach 3: Space-Optimized Dynamic Programming (Time: O(n*k), Space: O(k))
Each DP row depends only on the previous row. Instead of storing the entire n x k table, maintain two arrays or update a single array from right to left. This reduces memory usage from O(n*k) to O(k) while preserving the same recurrence. The update order is critical to avoid overwriting values that are still needed in the current iteration.
Recommended for interviews: Interviewers typically expect the dynamic programming recurrence. Explaining how the tallest stick either creates a new visible stick or gets hidden shows strong combinatorial reasoning. Implementing the bottom-up DP demonstrates solid problem-solving skills, while mentioning the O(k) space optimization shows deeper mastery.
Approach 1: Dynamic Programming Approach
This approach uses dynamic programming to efficiently calculate the number of arrangements. Define a DP table where dp[i][j] represents the number of ways to arrange i sticks with j sticks visible. The relation can be calculated as:
- If the largest stick among the
isticks is placed such that it's visible, the problem reduces to arranging the firsti-1sticks withj-1visible sticks. - If it's not visible, it can be placed in any of the
i-1positions, reducing the problem to arrangingi-1sticks withjvisible sticks.
The formula is then: dp[i][j] = dp[i-1][j-1] + (i-1) * dp[i-1][j].
def rearrangeSticks(n, k):
MOD = 10**9 + 7
dp = [[0] * (k+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1, n+1):
for j in range(1, k+1):
dp[i][j] = (dp[i-1][j-1] + (i-1) * dp[i-1][j]) % MOD
return dp[n][k]
print(rearrangeSticks(3, 2)) # Output: 3class Solution {
private static final int MOD = 1000000007;
public int rearrangeSticks(int n, int k) {
int[][] dp = new int[n+1][k+1];
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
dp[i][j] = (int)((dp[i-1][j-1] + (long)(i-1) * dp[i-1][j] % MOD) % MOD);
}
}
return dp[n][k];
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.rearrangeSticks(3, 2)); // Output: 3
}
}#include <iostream>
#include <vector>
#define MOD 1000000007
int rearrangeSticks(int n, int k) {
std::vector<std::vector<int>> dp(n+1, std::vector<int>(k+1, 0));
dp[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= k; ++j) {
dp[i][j] = (dp[i-1][j-1] + (long long)(i-1) * dp[i-1][j] % MOD) % MOD;
}
}
return dp[n][k];
}
int main() {
int n = 3, k = 2;
std::cout << rearrangeSticks(n, k) << std::endl;
return 0;
}function rearrangeSticks(n, k) {
const MOD = 1000000007;
const dp = Array.from({length: n+1}, () => Array(k+1).fill(0));
dp[0][0] = 1;
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= k; j++) {
dp[i][j] = (dp[i-1][j-1] + (i-1) * dp[i-1][j]) % MOD;
}
}
return dp[n][k];
}
console.log(rearrangeSticks(3, 2)); // Output: 3#include <stdio.h>
#define MOD 1000000007
int rearrangeSticks(int n, int k) {
int dp[n+1][k+1];
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= k; ++j)
dp[i][j] = 0;
dp[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= k; ++j) {
dp[i][j] = ((long long)dp[i-1][j-1] + (long long)(i-1) * dp[i-1][j] % MOD) % MOD;
}
}
return dp[n][k];
}
int main() {
int n = 3, k = 2;
printf("%d\n", rearrangeSticks(n, k));
return 0;
}using System;
public class Solution
{
private const int MOD = 1000000007;
public int RearrangeSticks(int n, int k)
{
int[,] dp = new int[n+1, k+1];
dp[0, 0] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= k; j++)
{
dp[i, j] = (int)((dp[i-1, j-1] + (long)(i-1) * dp[i-1, j] % MOD) % MOD);
}
}
return dp[n, k];
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.RearrangeSticks(3, 2)); // Output: 3
}
}In Python, the dynamic programming table is initialized using a list comprehension. The approach builds the solution iteratively while applying the modulo operation to avoid overflow.
The time complexity is O(n*k) and the space complexity is also O(n*k).
Approach 2: Dynamic Programming
We define f[i][j] to represent the number of permutations of length i in which exactly j sticks can be seen. Initially, f[0][0]=1 and the rest f[i][j]=0. The answer is f[n][k].
Consider whether the last stick can be seen. If it can be seen, it must be the longest. Then there are i - 1 sticks in front of it, and exactly j - 1 sticks can be seen, which is f[i - 1][j - 1]. If the last stick cannot be seen, it can be any one except the longest stick. Then there are i - 1 sticks in front of it, and exactly j sticks can be seen, which is f[i - 1][j] times (i - 1).
Therefore, the state transition equation is:
$
f[i][j] = f[i - 1][j - 1] + f[i - 1][j] times (i - 1)
The final answer is f[n][k].
The time complexity is O(n times k), and the space complexity is O(n times k). Where n and k$ are the two integers given in the problem.
function rearrangeSticks(n: number, k: number): number {
const mod = 10 ** 9 + 7;
const f: number[][] = Array.from({ length: n + 1 }, () =>
Array.from({ length: k + 1 }, () => 0),
);
f[0][0] = 1;
for (let i = 1; i <= n; ++i) {
for (let j = 1; j <= k; ++j) {
f[i][j] = (f[i - 1][j - 1] + (i - 1) * f[i - 1][j]) % mod;
}
}
return f[n][k];
}func rearrangeSticks(n int, k int) int {
const mod = 1e9 + 7
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, k+1)
}
f[0][0] = 1
for i := 1; i <= n; i++ {
for j := 1; j <= k; j++ {
f[i][j] = (f[i-1][j-1] + (i-1)*f[i-1][j]) % mod
}
}
return f[n][k]
}Approach 3: Dynamic Programming (Space Optimization)
We notice that f[i][j] is only related to f[i - 1][j - 1] and f[i - 1][j], so we can use a one-dimensional array to optimize the space complexity.
The time complexity is O(n times k), and the space complexity is O(k). Here, n and k are the two integers given in the problem.
function rearrangeSticks(n: number, k: number): number {
const mod = 10 ** 9 + 7;
const f: number[] = Array(n + 1).fill(0);
f[0] = 1;
for (let i = 1; i <= n; ++i) {
for (let j = k; j; --j) {
f[j] = (f[j] * (i - 1) + f[j - 1]) % mod;
}
f[0] = 0;
}
return f[k];
}func rearrangeSticks(n int, k int) int {
const mod = 1e9 + 7
f := make([]int, k+1)
f[0] = 1
for i := 1; i <= n; i++ {
for j := k; j > 0; j-- {
f[j] = (f[j-1] + f[j]*(i-1)) % mod
}
f[0] = 0
}
return f[k]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | The time complexity is |
| Dynamic Programming | – |
| Dynamic Programming (Space Optimization) | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive DP with Memoization | O(n*k) | O(n*k) | When deriving the recurrence or explaining the combinatorial reasoning during interviews |
| Bottom-Up Dynamic Programming | O(n*k) | O(n*k) | Standard implementation for competitive programming and production solutions |
| Space Optimized DP | O(n*k) | O(k) | When memory usage matters or when optimizing large DP tables |
Frequently asked questions
Is Number of Ways to Rearrange Sticks With K Sticks Visible easy or hard?
LeetCode classifies this problem as Hard. The challenge comes from recognizing the combinatorial recurrence and translating it into an efficient dynamic programming solution with correct state transitions.
Number of Ways to Rearrange Sticks With K Sticks Visible Python/Java solution
The solution in Python or Java implements the DP recurrence dp[n][k] = dp[n-1][k-1] + (n-1) * dp[n-1][k]. A loop fills the table from smaller stick counts to larger ones while applying modulo 1e9+7 to prevent overflow. Both languages achieve O(n*k) time complexity.
How to solve Number of Ways to Rearrange Sticks With K Sticks Visible in O(n*k)?
Define dp[i][j] as the number of ways to arrange i sticks with j visible. When adding the tallest stick, either place it first to increase visibility (dp[i-1][j-1]) or insert it among the other i-1 positions so it becomes hidden ((i-1) * dp[i-1][j]). Iteratively fill the DP table while taking modulo 1e9+7.
What is the best approach for Number of Ways to Rearrange Sticks With K Sticks Visible?
Dynamic programming using the recurrence dp[n][k] = dp[n-1][k-1] + (n-1) * dp[n-1][k] is the optimal approach. It models whether the tallest stick becomes visible or is hidden among the remaining positions. The algorithm runs in O(n*k) time and uses either O(n*k) or O(k) space depending on the implementation.
Is Number of Ways to Rearrange Sticks With K Sticks Visible asked at Google/Amazon/Meta?
Permutation counting and dynamic programming problems like this commonly appear in interviews at companies such as Google, Amazon, and Meta. The question tests understanding of combinatorial reasoning, recurrence relations, and DP optimization.
What data structure is used in Number of Ways to Rearrange Sticks With K Sticks Visible?
The main data structure is a dynamic programming table or array storing counts for states (n, k). Each state represents the number of permutations with a specific number of visible sticks. The implementation typically uses a 2D array or a 1D rolling array.
What is the time complexity of Number of Ways to Rearrange Sticks With K Sticks Visible?
The optimal dynamic programming solution runs in O(n*k) time because each state dp[i][j] is computed once using constant-time transitions. The DP table has n*k states. Space complexity is O(n*k) for the full table or O(k) with space optimization.