1866. Number of Ways to Rearrange Sticks With K Sticks Visible

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 10⁹ + 7.

Example: 1

Input: n = 3, k = 2

Output: 3

Example: 2

Input: n = 5, k = 5

Output: 1

Example: 3

Input: n = 20, k = 11

Output: 647427950

Constraints:

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

Some random thought process:

• We have to arrange the sticks in such a way that exactly k sticks are visible.
• A stick is only visible if and only if it has all other sticks smaller than it on it's left side.
• This observation paves way to a solution. It is as follows :
• If I have sticks numbered from 1 to n, and we try placing each stick to the end (rightmost side), we can see that stick from 1 to n - 1 won't be visible if they are placed at the last position. But placing the nth stick at last position doesn't affect the visibility of other sticks, because nth stick is the largest stick.

Conclusions from the above observations:

Two conclusions can be derived from the above observation:

If we have n sticks and exactly k out of the should be visible... then...

• If we place any stick smaller than n at the last position, then, we still have to make k sticks visible(because the stick at last position is invisible), but number of sticks will reduce by 1(because the last stick became invisible it cannot be used further).
• If we place any stick equal to the size of n at last position, then, this stick will be visible. So now we have to calculate number of ways to find (k - 1) sticks visible out of (n - 1) sticks.

Some base cases:

• If n == k, then number of ways will be equal to 1. This is because only ascendingly sorted order can provide k visible sticks from a total of k stick (n == k).
• If k > n, then number of ways equals 0 since the required state cannot be achieved.

Naive implementation using the above observations (will give TLE):

• Let's consider our function to be f(n, k).
• We will try to put each stick from 1 to n at the last position.
• If we are placing the nth stick at last position, then f(n, k) will recur to f(n - 1, k - 1).
• If we are placing any other stick whose value is less than n, then f(n, k) will recur to f(n - 1, k).

Naive implementation using DP: class Solution { long mod = 1000_000_000 + 7; Long[][] dp; public int rearrangeSticks(int n, int k) { dp = new Long[n + 1][k + 1]; long ans = recur(n, k); return (int) (ans % mod); } long recur(int n, int k) { if(n < k || k == 0) return 0; if(n == k) return 1; if(dp[n][k] != null) return dp[n][k]; long ans = 0; // trying each stick from 1 to n // placing them at last position for(int N = 1; N <= n; N++) { if(N == n) { // if the current stick is largest ans += recur(n - 1, k - 1); } else { // if the current stick is not largest ans += recur(n - 1, k); } ans %= mod; } dp[n][k] = ans; return ans; } }

Changing TLE to Accepted:

• Now we can see clearly that stick 1 to n - 1 will always form a function f(n - 1, k).
• So we don't have to iterate through it again and again.
• We will simply multiply the answer we get by placing stick 1 at the last position by (n - 1).
• This will reduce our iterations step and thus bring the problem to O(n * k) from O(n * n * k).

Full Code (Java): class Solution { long mod = 1000_000_000 + 7; long[][] dp; public int rearrangeSticks(int n, int k) { dp = new long[n + 1][k + 1]; long ans = recur(n, k); return (int) (ans % mod); } long recur(int n, int k) { if(n < k || k == 0) return 0; if(n == k) return 1; if(dp[n][k] != 0) return dp[n][k]; long ans = 0; // instead of iterating for every stick // we are just multiplying number of ways with (n - 1) ans += (((n - 1) * recur(n - 1, k)) % mod); ans %= mod; ans += recur(n - 1, k - 1); ans %= mod; dp[n][k] = ans; return ans; } }