Skip to main content
Talentd

Number of Ways to Rearrange Sticks With K Sticks Visible - Solution & Explanation

HardMathDynamic ProgrammingCombinatorics18 min readAsked at: Google
Practice this problem

Problem Statement

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

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 i sticks is placed such that it's visible, the problem reduces to arranging the first i-1 sticks with j-1 visible sticks.
  • If it's not visible, it can be placed in any of the i-1 positions, reducing the problem to arranging i-1 sticks with j visible sticks.

The formula is then: dp[i][j] = dp[i-1][j-1] + (i-1) * dp[i-1][j].

This C solution initializes a 2D array to store computation results for n sticks and k visible sticks. The array is filled using the relationship described earlier, and the final result is modulo 10^9 + 7 to handle large numbers.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity is O(n*k) and the space complexity is also O(n*k).

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

The time complexity is O(n*k) and the space complexity is also O(n*k).

Dynamic Programming—
Dynamic Programming (Space Optimization)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive DP with MemoizationO(n*k)O(n*k)When deriving the recurrence or explaining the combinatorial reasoning during interviews
Bottom-Up Dynamic ProgrammingO(n*k)O(n*k)Standard implementation for competitive programming and production solutions
Space Optimized DPO(n*k)O(k)When memory usage matters or when optimizing large DP tables

Video Solution

Number of Ways to Rearrange Sticks With K Sticks Visible - Dynamic Programming - Leetcode 1866 • NeetCode • 17,716 views views

Watch 8 more video solutions →

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.

Ready to solve this problem?

Practice Number of Ways to Rearrange Sticks With K Sticks Visible with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer