Number of Sets of K Non-Overlapping Line Segments
MedPrompt
Given n points on a 1-D plane, where the ith point (from 0 to n-1) is at x = i, find the number of ways we can draw exactly k non-overlapping line segments such that each segment covers two or more points. The endpoints of each segment must have integral coordinates. The k line segments do not have to cover all n points, and they are allowed to share endpoints.
Return the number of ways we can draw k non-overlapping line segments. Since this number can be huge, return it modulo 109 + 7.
Example 1:
Input: n = 4, k = 2
Output: 5
Explanation: The two line segments are shown in red and blue.
The image above shows the 5 different ways {(0,2),(2,3)}, {(0,1),(1,3)}, {(0,1),(2,3)}, {(1,2),(2,3)}, {(0,1),(1,2)}.Example 2:
Input: n = 3, k = 1
Output: 3
Explanation: The 3 ways are {(0,1)}, {(0,2)}, {(1,2)}.Example 3:
Input: n = 30, k = 7
Output: 796297179
Explanation: The total number of possible ways to draw 7 line segments is 3796297200. Taking this number modulo 109 + 7 gives us 796297179.
Constraints:
2 <= n <= 10001 <= k <= n-1
Approaches
3 approaches with complexity analysis and trade-offs.
The most efficient solution involves reframing the problem from a dynamic programming perspective to a combinatorial one. The problem of choosing k non-overlapping line segments can be mapped to a problem of choosing 2k numbers from a specific range. This transformation, a variant of the 'stars and bars' method, leads to a direct mathematical formula for the answer, which can be computed very efficiently.
Algorithm
- Realize the problem is equivalent to a combinatorial selection problem.
- The condition
0 <= s_1 < e_1 <= s_2 < ... <= s_k < e_k <= n-1can be transformed into a strictly increasing sequence0 <= z_1 < z_2 < ... < z_{2k} <= n+k-2. - This is equivalent to choosing
2kdistinct numbers from the set{0, 1, ..., n+k-2}, which hasn+k-1elements. - The number of ways is given by the binomial coefficient
C(n+k-1, 2k). - To compute
C(N, K) mod PwherePis prime, we use the formula(N! * inv(K!) * inv((N-K)!)) mod P. - Precompute factorials and their modular inverses up to
n+k-1. - Calculate the final result using the precomputed values.
Walkthrough
Let the k non-overlapping segments be [s_1, e_1], [s_2, e_2], ..., [s_k, e_k]. By the problem definition, we can order them such that:
0 <= s_1 < e_1 <= s_2 < e_2 <= ... <= s_k < e_k <= n-1
This is a sequence of 2k integers with a mix of strict (<) and non-strict (<=) inequalities. We can convert this into a problem of choosing 2k distinct integers by applying a transformation. Let's define a new sequence z_1, z_2, ..., z_{2k} as follows:
z_1 = s_1z_2 = e_1z_3 = s_2 + 1z_4 = e_2 + 1- ...
z_{2i-1} = s_i + i - 1z_{2i} = e_i + i - 1
This transformation cleverly converts the original sequence into a strictly increasing sequence: 0 <= z_1 < z_2 < ... < z_{2k}.
The upper bound for z_{2k} is e_k + k - 1. Since e_k <= n-1, we have z_{2k} <= (n-1) + (k-1) = n+k-2.
So, the problem is now equivalent to choosing 2k distinct numbers from the range [0, n+k-2]. The total count of numbers in this range is (n+k-2) - 0 + 1 = n+k-1.
The number of ways to choose 2k distinct numbers from n+k-1 numbers is given by the binomial coefficient C(n+k-1, 2k).
We can compute C(N, K) = N! / (K! * (N-K)!) modulo 10^9 + 7. Since 10^9 + 7 is a prime number, we can precompute factorials and their modular inverses (using Fermat's Little Theorem) to find the answer efficiently.
class Solution { public int numberOfSets(int n, int k) { int MOD = 1_000_000_007; int N = n + k - 1; int K = 2 * k; if (K > N) { return 0; } // Calculate C(N, K) % MOD long[] fact = new long[N + 1]; long[] invFact = new long[N + 1]; fact[0] = 1; invFact[0] = 1; for (int i = 1; i <= N; i++) { fact[i] = (fact[i - 1] * i) % MOD; } invFact[N] = power(fact[N], MOD - 2, MOD); for (int i = N - 1; i >= 1; i--) { invFact[i] = (invFact[i + 1] * (i + 1)) % MOD; } long numerator = fact[N]; long denominator = (invFact[K] * invFact[N - K]) % MOD; return (int) ((numerator * denominator) % MOD); } private long power(long base, long exp, int mod) { long res = 1; base %= mod; while (exp > 0) { if (exp % 2 == 1) res = (res * base) % mod; base = (base * base) % mod; exp /= 2; } return res; }}Complexity
Time
O(n + k + log(MOD)). The dominant part is the precomputation of factorials, which takes O(n+k). The modular inverse calculation takes O(log(MOD)). After precomputation, the answer is found in O(1).
Space
O(n + k) to store the precomputed factorials and inverse factorials.
Trade-offs
Pros
Extremely efficient, with a time complexity that is linear in
n+kfor precomputation.Provides a direct, closed-form solution.
Elegant mathematical approach.
Cons
The combinatorial insight (stars and bars transformation) can be difficult to derive.
Requires knowledge of modular arithmetic, including combinations and modular multiplicative inverse.
Solutions
Solution
class Solution {private static final int MOD = (int)1 e9 + 7;public int numberOfSets(int n, int k) { int[][] f = new int[n + 1][k + 1]; int[][] g = new int[n + 1][k + 1]; f[1][0] = 1; for (int i = 2; i <= n; ++i) { for (int j = 0; j <= k; ++j) { f[i][j] = (f[i - 1][j] + g[i - 1][j]) % MOD; g[i][j] = g[i - 1][j]; if (j > 0) { g[i][j] += f[i - 1][j - 1]; g[i][j] %= MOD; g[i][j] += g[i - 1][j - 1]; g[i][j] %= MOD; } } } return (f[n][k] + g[n][k]) % MOD; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.