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.
This approach uses a straightforward dynamic programming solution. We build the solution incrementally by considering one point at a time. The state of our DP, dp[i][j], represents the number of ways to form j segments using the first i points. The transition involves a summation over all possible start points for a new segment ending at the current point, which leads to a cubic time complexity.
Algorithm
- Create a 2D DP table
dp[n+1][k+1]to store the number of ways. dp[i][j]will store the number of ways to placejsegments using the firstipoints (from0toi-1).- Initialize the base cases:
dp[i][0] = 1for alli, as there's one way to place zero segments (by doing nothing). - Iterate through the points
ifrom 1 ton. - For each
i, iterate through the number of segmentsjfrom 1 tok. - The value of
dp[i][j]is calculated based on two possibilities for pointi-1:- Point
i-1is not used as an endpoint. The number of ways isdp[i-1][j]. - Point
i-1is the right endpoint of thej-th segment. This segment can be[p, i-1]for any0 <= p < i-1. The previousj-1segments must be placed using points0top. The number of ways for this isdp[p+1][j-1]. We sum this over all possiblep.
- Point
- The recurrence is:
dp[i][j] = dp[i-1][j] + sum_{p=0}^{i-2} dp[p+1][j-1]. - The final answer is
dp[n][k].
Walkthrough
Let dp[i][j] be the number of ways to place j non-overlapping segments using the first i points (i.e., points 0, 1, ..., i-1).
To compute dp[i][j], we consider two cases for the i-th point (coordinate i-1):
- Point
i-1is not used as an endpoint: In this case, alljsegments must be formed using the firsti-1points (0, ..., i-2). The number of ways for this is simplydp[i-1][j]. - Point
i-1is the right endpoint of a new segment: This new segment must be thej-th segment. Let's say it is[p, i-1], where0 <= p < i-1. The remainingj-1segments must be formed using points0, ..., p. The number of ways to do this isdp[p+1][j-1]. Sincepcan be any point from0toi-2, we must sum the ways for all possible start points.
This logic gives us the recurrence relation:
dp[i][j] = dp[i-1][j] + sum_{p=0}^{i-2} dp[p+1][j-1]
The base cases are dp[i][0] = 1 for all i >= 1 (one way to place zero segments) and dp[0][j] = 0 for j > 0. The final answer is dp[n][k].
The implementation requires three nested loops: one for i (from 1 to n), one for j (from 1 to k), and an inner loop for the summation over p (from 0 to i-2).
class Solution { public int numberOfSets(int n, int k) { int MOD = 1_000_000_007; long[][] dp = new long[n + 1][k + 1]; for (int i = 0; i <= n; i++) { dp[i][0] = 1; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= k; j++) { // Case 1: Point i-1 is not used dp[i][j] = dp[i - 1][j]; // Case 2: Point i-1 is the right endpoint of the j-th segment for (int p = 0; p < i - 1; p++) { // Segment is [p, i-1]. j-1 segments must be placed using points 0..p // which means using p+1 points. dp[i][j] = (dp[i][j] + dp[p + 1][j - 1]) % MOD; } } } return (int) dp[n][k]; }}Complexity
Time
O(n^2 * k). The three nested loops for `i` (up to `n`), `j` (up to `k`), and `p` (up to `n`) result in a cubic time complexity.
Space
O(n * k) to store the 2D DP table.
Trade-offs
Pros
Conceptually simple and directly follows the problem's recursive structure.
Cons
Very high time complexity, which will result in a 'Time Limit Exceeded' error for the given constraints.
This approach improves upon the naive DP by optimizing the recurrence relation. The inner loop, which calculates a summation, can be eliminated by observing the relationship between dp[i][j] and dp[i-1][j]. This mathematical trick allows us to compute each DP state in constant time, reducing the overall time complexity from cubic to quadratic.
Algorithm
- The recurrence from the naive approach is
dp[i][j] = dp[i-1][j] + sum_{q=1}^{i-1} dp[q][j-1]. - Observe that the summation term can be eliminated. Write the recurrence for
dp[i-1][j]:dp[i-1][j] = dp[i-2][j] + sum_{q=1}^{i-2} dp[q][j-1]. - Subtract the second equation from the first:
dp[i][j] - dp[i-1][j] = (dp[i-1][j] - dp[i-2][j]) + dp[i-1][j-1]. - Rearrange to get the optimized recurrence:
dp[i][j] = 2 * dp[i-1][j] - dp[i-2][j] + dp[i-1][j-1]. - Create a 2D DP table
dp[n+1][k+1]and initialize base casesdp[i][0] = 1. - Iterate
ifrom 2 tonandjfrom 1 tok, filling the table using the new recurrence. - Return
dp[n][k].
Walkthrough
We start with the same recurrence as the naive approach:
dp[i][j] = dp[i-1][j] + sum_{q=1}^{i-1} dp[q][j-1]
Let's analyze the summation part. We can express dp[i-1][j] similarly:
dp[i-1][j] = dp[i-2][j] + sum_{q=1}^{i-2} dp[q][j-1]
Notice that sum_{q=1}^{i-1} dp[q][j-1] = sum_{q=1}^{i-2} dp[q][j-1] + dp[i-1][j-1].
By subtracting the second recurrence from the first, we get:
dp[i][j] - dp[i-1][j] = (dp[i-1][j] - dp[i-2][j]) + dp[i-1][j-1]
Rearranging the terms gives us a new, more efficient recurrence that doesn't involve a summation:
dp[i][j] = 2 * dp[i-1][j] - dp[i-2][j] + dp[i-1][j-1]
Using this recurrence, each state dp[i][j] can be computed in O(1) time. We still need to fill an n x k table, so the total time complexity becomes O(n * k). When implementing, we must be careful with modular arithmetic, especially subtraction, by adding MOD before taking the modulus to handle potential negative results.
class Solution { public int numberOfSets(int n, int k) { int MOD = 1_000_000_007; long[][] dp = new long[n + 1][k + 1]; for (int i = 0; i <= n; i++) { dp[i][0] = 1; } for (int i = 2; i <= n; i++) { for (int j = 1; j <= k; j++) { // dp[i][j] = 2 * dp[i-1][j] - dp[i-2][j] + dp[i-1][j-1] long val = (2 * dp[i - 1][j]) % MOD; val = (val - dp[i - 2][j] + MOD) % MOD; // Add MOD to handle negative results val = (val + dp[i - 1][j - 1]) % MOD; dp[i][j] = val; } } return (int) dp[n][k]; }}This approach is efficient enough to pass within the given constraints.
Complexity
Time
O(n * k). We iterate through the `n x k` DP table, and each state is computed in O(1) time.
Space
O(n * k) for the DP table. This can be optimized to O(k) by noticing that `dp[i]` only depends on `dp[i-1]` and `dp[i-2]`, so we only need to store the two previous rows.
Trade-offs
Pros
Significantly more efficient than the naive DP approach.
Passes the time limits for the given constraints.
Cons
The derivation of the recurrence is less intuitive.
Requires careful handling of indices and modular arithmetic to avoid errors.
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; }}class Solution {public: int f[1010][1010]; int g[1010][1010]; const int mod = 1e9 + 7; int numberOfSets(int n, int k) { memset(f, 0, sizeof(f)); memset(g, 0, sizeof(g)); 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; }};class Solution: def numberOfSets(self, n: int, k: int) -> int: mod = 10 ** 9 + 7 f = [[0] * (k + 1) for _ in range(n + 1)] g = [[0] * (k + 1) for _ in range(n + 1)] f[1][0] = 1 for i in range(2, n + 1): for j in range(k + 1): f[i][j] = (f[i - 1][j] + g[i - 1][j]) % mod g[i][j] = g[i - 1][j] if j: 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[- 1][- 1] + g[- 1][- 1]) % modVideo 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.