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 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^9 + 7.

Examples

Example 1:

1
2
3
4
5
6

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:

1
2
3
4
5
6

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:

1
2
3
4
5

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

Solution

Method 1 - Recursion

We need to arrange the sticks so that exactly k sticks are visible from the left. A stick is visible only if all sticks to its left are shorter.

Key observations:

  • If we have n sticks and want exactly k visible:
    • Placing any stick smaller than n at the last position means it will be hidden, so we still need k visible sticks among the remaining n-1 sticks.
    • Placing the largest stick (n) at the last position guarantees it is visible, so we need k-1 visible sticks among the remaining n-1 sticks.

Base cases:

  • If n == k, only one way (sorted order).
  • If k == 0 or n == 0, ways = 0.
  • If k > n, ways = 0 (impossible).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
	int rearrangeSticks(int n, int k) {
		int mod = 1e9 + 7;
		return dfs(n, k, mod);
	}
	int dfs(int n, int k, int mod) {
		if (n == k) return 1;
		if (k == 0 || n == 0 || k > n) return 0;
		long res = (long)(n - 1) * dfs(n - 1, k, mod) % mod;
		res = (res + dfs(n - 1, k - 1, mod)) % mod;
		return (int)res;
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func rearrangeSticks(n int, k int) int {
	mod := int(1e9 + 7)
	var dfs func(int, int) int
	dfs = func(n, k int) int {
		if n == k {
			return 1
		}
		if k == 0 || n == 0 || k > n {
			return 0
		}
		res := (n-1)*dfs(n-1, k)%mod
		res = (res + dfs(n-1, k-1))%mod
		return res
	}
	return dfs(n, k)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
	public int rearrangeSticks(int n, int k) {
		int mod = (int)1e9 + 7;
		return dfs(n, k, mod);
	}
	private int dfs(int n, int k, int mod) {
		if (n == k) return 1;
		if (k == 0 || n == 0 || k > n) return 0;
		long res = (long)(n - 1) * dfs(n - 1, k, mod) % mod;
		res = (res + dfs(n - 1, k - 1, mod)) % mod;
		return (int)res;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
	fun rearrangeSticks(n: Int, k: Int): Int {
		val mod = 1_000_000_007
		fun dfs(n: Int, k: Int): Int {
			if (n == k) return 1
			if (k == 0 || n == 0 || k > n) return 0
			var res = ((n - 1).toLong() * dfs(n - 1, k) % mod)
			res = (res + dfs(n - 1, k - 1)) % mod
			return res.toInt()
		}
		return dfs(n, k)
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
	def rearrangeSticks(self, n: int, k: int) -> int:
		mod = 10**9 + 7
		def dfs(n: int, k: int) -> int:
			if n == k:
				return 1
			if k == 0 or n == 0 or k > n:
				return 0
			res = (n - 1) * dfs(n - 1, k) % mod
			res = (res + dfs(n - 1, k - 1)) % mod
			return res
		return dfs(n, k)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
	pub fn rearrange_sticks(n: i32, k: i32) -> i32 {
		fn dfs(n: i32, k: i32, modv: i32) -> i32 {
			if n == k { return 1; }
			if k == 0 || n == 0 || k > n { return 0; }
			let mut res = ((n - 1) as i64 * dfs(n - 1, k, modv) as i64) % (modv as i64);
			res = (res + dfs(n - 1, k - 1, modv) as i64) % (modv as i64);
			res as i32
		}
		dfs(n, k, 1_000_000_007)
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
	rearrangeSticks(n: number, k: number): number {
		const mod = 1e9 + 7;
		function dfs(n: number, k: number): number {
			if (n === k) return 1;
			if (k === 0 || n === 0 || k > n) return 0;
			let res = ((n - 1) * dfs(n - 1, k)) % mod;
			res = (res + dfs(n - 1, k - 1)) % mod;
			return res;
		}
		return dfs(n, k);
	}
}

Complexity

  • ⏰ Time complexity: O(2^n), since each call can branch into two subproblems and there are no memoized results.
  • 🧺 Space complexity: O(n), due to recursion stack.

Method 2 - Top-Down DP + Memoization

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
	int rearrangeSticks(int n, int k) {
		int mod = 1e9 + 7;
		vector<vector<int>> memo(n + 1, vector<int>(k + 1, -1));
		return dfs(n, k, mod, memo);
	}
	int dfs(int n, int k, int mod, vector<vector<int>>& memo) {
		if (n == k) return 1;
		if (k == 0 || n == 0 || k > n) return 0;
		if (memo[n][k] != -1) return memo[n][k];
		long res = (long)(n - 1) * dfs(n - 1, k, mod, memo) % mod;
		res = (res + dfs(n - 1, k - 1, mod, memo)) % mod;
		memo[n][k] = (int)res;
		return memo[n][k];
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func rearrangeSticks(n int, k int) int {
	mod := int(1e9 + 7)
	memo := make(map[[2]int]int)
	var dfs func(int, int) int
	dfs = func(n, k int) int {
		if n == k {
			return 1
		}
		if k == 0 || n == 0 || k > n {
			return 0
		}
		key := [2]int{n, k}
		if v, ok := memo[key]; ok {
			return v
		}
		res := (n-1)*dfs(n-1, k)%mod
		res = (res + dfs(n-1, k-1))%mod
		memo[key] = res
		return res
	}
	return dfs(n, 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) {
		int mod = (int)1e9 + 7;
		Integer[][] memo = new Integer[n + 1][k + 1];
		return dfs(n, k, mod, memo);
	}
	private int dfs(int n, int k, int mod, Integer[][] memo) {
		if (n == k) return 1;
		if (k == 0 || n == 0 || k > n) return 0;
		if (memo[n][k] != null) return memo[n][k];
		long res = (long)(n - 1) * dfs(n - 1, k, mod, memo) % mod;
		res = (res + dfs(n - 1, k - 1, mod, memo)) % mod;
		memo[n][k] = (int)res;
		return memo[n][k];
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
	fun rearrangeSticks(n: Int, k: Int): Int {
		val mod = 1_000_000_007
		val memo = Array(n + 1) { Array(k + 1) { -1 } }
		fun dfs(n: Int, k: Int): Int {
			if (n == k) return 1
			if (k == 0 || n == 0 || k > n) return 0
			if (memo[n][k] != -1) return memo[n][k]
			var res = ((n - 1).toLong() * dfs(n - 1, k) % mod)
			res = (res + dfs(n - 1, k - 1)) % mod
			memo[n][k] = res.toInt()
			return memo[n][k]
		}
		return dfs(n, k)
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
	def rearrangeSticks(self, n: int, k: int) -> int:
		mod = 10**9 + 7
		memo = {}
		def dfs(n: int, k: int) -> int:
			if n == k:
				return 1
			if k == 0 or n == 0 or k > n:
				return 0
			if (n, k) in memo:
				return memo[(n, k)]
			res = (n - 1) * dfs(n - 1, k) % mod
			res = (res + dfs(n - 1, k - 1)) % mod
			memo[(n, k)] = res
			return res
		return dfs(n, k)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
	pub fn rearrange_sticks(n: i32, k: i32) -> i32 {
		fn dfs(n: i32, k: i32, modv: i32, memo: &mut Vec<Vec<i32>>) -> i32 {
			if n == k { return 1; }
			if k == 0 || n == 0 || k > n { return 0; }
			if memo[n as usize][k as usize] != -1 { return memo[n as usize][k as usize]; }
			let mut res = ((n - 1) as i64 * dfs(n - 1, k, modv, memo) as i64) % (modv as i64);
			res = (res + dfs(n - 1, k - 1, modv, memo) as i64) % (modv as i64);
			memo[n as usize][k as usize] = res as i32;
			res as i32
		}
		let mut memo = vec![vec![-1; (k + 1) as usize]; (n + 1) as usize];
		dfs(n, k, 1_000_000_007, &mut memo)
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
	rearrangeSticks(n: number, k: number): number {
		const mod = 1e9 + 7;
		const memo: Record<string, number> = {};
		function dfs(n: number, k: number): number {
			if (n === k) return 1;
			if (k === 0 || n === 0 || k > n) return 0;
			const key = `${n},${k}`;
			if (memo[key] !== undefined) return memo[key];
			let res = ((n - 1) * dfs(n - 1, k)) % mod;
			res = (res + dfs(n - 1, k - 1)) % mod;
			memo[key] = res;
			return res;
		}
		return dfs(n, k);
	}
}

Complexity

  • ⏰ Time complexity: O(nk), since each subproblem (n, k) is solved only once and stored in the memoization table.
  • 🧺 Space complexity: O(nk), for the memoization table and recursion stack.

Method 3 - Bottom-Up DP (Tabulation)

Intuition

We use a DP table to build the solution iteratively. For each number of sticks and visible sticks, we compute the number of arrangements using previously computed results, avoiding recursion and memoization.

Approach

  1. Create a DP table dp[n+1][k+1] where dp[i][j] is the number of ways to arrange i sticks with j visible.
  2. Initialize dp[0][0] = 1 (base case).
  3. For each i from 1 to n, and each j from 1 to min(i, k), compute:
    • dp[i][j] = (dp[i-1][j] * (i-1) + dp[i-1][j-1]) % mod
    • First term: place a smaller stick at the end (hidden), second term: place the largest stick at the end (visible).
  4. Return dp[n][k].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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

func rearrangeSticks(n int, k int) int {
	mod := int(1e9 + 7)
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, k+1)
	}
	dp[0][0] = 1
	for i := 1; i <= n; i++ {
		for j := 1; j <= k && j <= i; j++ {
			dp[i][j] = (dp[i-1][j]*(i-1) + dp[i-1][j-1]) % mod
		}
	}
	return dp[n][k]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

class Solution {
	fun rearrangeSticks(n: Int, k: Int): Int {
		val mod = 1_000_000_007
		val dp = Array(n + 1) { LongArray(k + 1) }
		dp[0][0] = 1L
		for (i in 1..n) {
			for (j in 1..minOf(i, k)) {
				dp[i][j] = (dp[i-1][j] * (i-1) + dp[i-1][j-1]) % mod
			}
		}
		return dp[n][k].toInt()
	}
}
1
2
3
4
5
6
7
8
9

class Solution:
	def rearrangeSticks(self, n: int, k: int) -> int:
		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, min(i, k) + 1):
				dp[i][j] = (dp[i-1][j] * (i-1) + dp[i-1][j-1]) % mod
		return dp[n][k]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
	pub fn rearrange_sticks(n: i32, k: i32) -> i32 {
		let modv = 1_000_000_007;
		let n = n as usize;
		let k = k as usize;
		let mut dp = vec![vec![0i64; k + 1]; n + 1];
		dp[0][0] = 1;
		for i in 1..=n {
			for j in 1..=k.min(i) {
				dp[i][j] = (dp[i-1][j] * (i as i64 - 1) + dp[i-1][j-1]) % modv;
			}
		}
		dp[n][k] as i32
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
	rearrangeSticks(n: number, k: number): number {
		const mod = 1e9 + 7;
		const dp: number[][] = 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 <= Math.min(i, k); j++) {
				dp[i][j] = (dp[i-1][j] * (i-1) + dp[i-1][j-1]) % mod;
			}
		}
		return dp[n][k];
	}
}

Complexity

  • ⏰ Time complexity: O(nk), since we fill a DP table of size n x k and each entry takes constant time.
  • 🧺 Space complexity: O(nk), for the DP table.