Skip to content

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

Description

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

Solutions

Solution 1: Dynamic Programming

Thinking

Count permutations of \(n\) sticks where exactly \(k\) are visible from the left. A stick is visible iff it is the tallest so far. \(n\le 1000\) forbids listing permutations.

Let \(f[i][j]\) be the ways among \(i\) sticks with \(j\) visible. Placing the tallest last always adds a visible stick; otherwise the last height is one of the other \(i-1\) values and the visible count stays the same. The recurrence yields \(f[n][k]\).

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.

1
2
3
4
5
6
7
8
9
class Solution:
    def rearrangeSticks(self, n: int, k: int) -> int:
        mod = 10**9 + 7
        f = [[0] * (k + 1) for _ in range(n + 1)]
        f[0][0] = 1
        for i in range(1, n + 1):
            for j in range(1, k + 1):
                f[i][j] = (f[i - 1][j - 1] + f[i - 1][j] * (i - 1)) % mod
        return f[n][k]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int rearrangeSticks(int n, int k) {
        final int mod = (int) 1e9 + 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];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int rearrangeSticks(int n, int k) {
        const int mod = 1e9 + 7;
        int f[n + 1][k + 1];
        memset(f, 0, sizeof(f));
        f[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= k; ++j) {
                f[i][j] = (f[i - 1][j - 1] + (i - 1LL) * f[i - 1][j]) % mod;
            }
        }
        return f[n][k];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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];
}

Solution 2: Dynamic Programming (Space Optimization)

Thinking

Solution 1's \(f[i][j]\) depends only on the previous row. Compress to one array and update \(j\) downward so \(f[j-1]\) is still the old value. Extra space becomes \(O(k)\).

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.

1
2
3
4
5
6
7
8
9
class Solution:
    def rearrangeSticks(self, n: int, k: int) -> int:
        mod = 10**9 + 7
        f = [1] + [0] * k
        for i in range(1, n + 1):
            for j in range(k, 0, -1):
                f[j] = (f[j] * (i - 1) + f[j - 1]) % mod
            f[0] = 0
        return f[k]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int rearrangeSticks(int n, int k) {
        final int mod = (int) 1e9 + 7;
        int[] f = new int[k + 1];
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = k; j > 0; --j) {
                f[j] = (int) ((f[j] * (i - 1L) + f[j - 1]) % mod);
            }
            f[0] = 0;
        }
        return f[k];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int rearrangeSticks(int n, int k) {
        const int mod = 1e9 + 7;
        int f[k + 1];
        memset(f, 0, sizeof(f));
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = k; j; --j) {
                f[j] = (f[j - 1] + f[j] * (i - 1LL)) % mod;
            }
            f[0] = 0;
        }
        return f[k];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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];
}

Comments