1621. Number of Sets of K Non-Overlapping Line Segments
Problem Description
This problem involves a set of points on a 1-D plane. Each point is designated by a unique integer position from 0 to n-1
, representing their placement on the line. We are interested in finding the number of ways to create k
line segments, where each line segment covers at least two points and has endpoints at integral coordinates. It's important to note that these line segments must be non-overlapping, though they can share endpoints. The goal is to calculate the number of distinct configurations you can draw with these requirements.
A crucial detail is that not all points need to be covered by the line segments; thus, some points can remain unused. Also, since the number of ways can be enormous, the solution should be given modulo 10^9 + 7
, a common practice in combinatorics-related problems to keep the numbers manageable.
Intuition
To approach this problem, consider dynamic programming, which is a method used to solve complex problems by breaking them down into simpler subproblems. The idea behind this approach is to create a table, with f
and g
to record the number of ways to satisfy the condition up to the i
-th point with j
segments used so far.
The 2D arrays f
and g
are critical in our dynamic programming approach. f[i][j]
represents the number of ways we can draw j
line segments up to the i
-th point, where the i
-th point is not shared with the next segment (an endpoint). In contrast, g[i][j]
counts the number of configurations where the i
-th point is shared (not the end of the last segment), allowing a segment to extend to include more points.
The key to solving the problem is to correctly update the values in f
and g
through iteration. Initially, we set f[1][0]
to 1, as there is only one way to have 0 segments with 1 point. Then we iterate through all points and all possible numbers of segments, updating f
based on previous values and g
based on both its previous value and the value of f
. If we're allowed to add a new segment (j
is greater than 0), we can look back at previous points and either start a new segment (f[i - 1][j - 1]
) or extend an existing one (g[i - 1][j - 1]
).
In short, f
and g
are used to accumulate the number of valid configurations as we progress through the points and segments, with the updates accounting for starting, ending, and extending segments at each step. The final answer consists of the sum of f[n][k]
and g[n][k]
, which are the number of configurations after considering all points and exactly k
segments, modulo 10^9 + 7
.
By setting up these relations and carefully calculating the iterations, we consider all possible segment configurations and meet the constraints of non-overlapping with the option of shared endpoints, efficiently arriving at the correct count.
Learn more about Math and Dynamic Programming patterns.
Solution Approach
The solution involves dynamic programming, which iteratively updates our two tables, f
and g
, to account for the various combinations of segments up to each point i
for 0
to n-1
and each possible number of segments j
from 0
to k
.
We start with the initialization:
1mod = 10**9 + 7
2f = [[0] * (k + 1) for _ in range(n + 1)]
3g = [[0] * (k + 1) for _ in range(n + 1)]
4f[1][0] = 1
Here, mod
is the number we'll use to perform modulus operations to keep our solution within the required range to avoid integer overflow. The tables f
and g
are initialized with zeros, since we start with no configurations, and set 1
for f[1][0]
since there's exactly 1
way to have 0
segments among 1
point.
Following the initialization, the main iteration begins:
1for i in range(2, n + 1):
2 for j in range(k + 1):
3 f[i][j] = (f[i - 1][j] + g[i - 1][j]) % mod
4 g[i][j] = g[i - 1][j]
For each point i
and each number of segments j
, we update f[i][j]
by the sum of the number of ways we can draw j
segments up to the previous point without it being an endpoint (f[i - 1][j]
) and the number of ways with it being a shared point (g[i - 1][j]
). Then, we carry over the value of g[i - 1][j]
to g[i][j]
because we can always extend a line segment to point i
without adding a new segment.
Additionally, if it's allowed to add a new segment (j > 0
), we have the following update rules:
1if j: 2 g[i][j] += f[i - 1][j - 1] 3 g[i][j] %= mod 4 g[i][j] += g[i - 1][j - 1] 5 g[i][j] %= mod
We increment g[i][j]
by the number of ways to draw j-1
segments up to the previous point, and add either a new segment end (f[i - 1][j - 1]
) or extend an existing segment (g[i - 1][j - 1]
). This accounts for all the possibilities at point i
with j
segments.
Finally, the return statement sums the number of configurations for n
points and k
segments from both tables:
1return (f[-1][-1] + g[-1][-1]) % mod
We use -1
as an index for convenience to refer to the last element of the list, which represents all points and exactly k
segments. The modulus operation ensures the result complies with the required number range.
Through this iterative and layered approach, the algorithm efficiently calculates the required configurations, respecting the rules of non-overlapping segments which can optionally share endpoints. This method leverages dynamic programming to handle numerous potential combinations, significantly reducing the time complexity compared to naively enumerating all possible segment configurations.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach.
Consider a set with n = 4
points and we want to find the number of ways to create k = 1
line segment. The points on the 1-D plane can be represented as [0, 1, 2, 3].
Using dynamic programming, we initialize our tables f
and g
like this:
1mod = 10**9 + 7
2n = 4
3k = 1
4f = [[0] * (k + 1) for _ in range(n + 1)]
5g = [[0] * (k + 1) for _ in range(n + 1)]
6f[1][0] = 1
After initialization, f
and g
look like this:
1f = [[0, 0], 2 [1, 0], 3 [0, 0], 4 [0, 0], 5 [0, 0]] 6 7g = [[0, 0], 8 [0, 0], 9 [0, 0], 10 [0, 0], 11 [0, 0]]
Now we start iterating over each point and potential number of segments:
- For
i = 2
,j = 1
:- There's no way to have a segment with just point [0] (
f[1][1] = 0
), sof[2][1]
remains0
. - Since
j > 0
, we add ways fromf[i-1][j-1]
tog[i][j]
, resulting ing[2][1]
becoming1
(one way to start a new segment at [1,2]).
- There's no way to have a segment with just point [0] (
At this point, our tables are:
1f = [[0, 0], 2 [1, 0], 3 [0, 0], 4 [0, 0], 5 [0, 0]] 6 7g = [[0, 0], 8 [0, 0], 9 [0, 1], 10 [0, 0], 11 [0, 0]]
- For
i = 3
,j = 1
:- Now
f[3][1]
becomes the sum off[2][1]
andg[2][1]
, which is1
. - We carry over
g[2][1]
tog[3][1]
. Sincej > 0
,g[3][1]
will also includef[2][0]
, but sincef[2][0]
is0
, it doesn't change.
- Now
Tables now:
1f = [[0, 0], 2 [1, 0], 3 [0, 1], 4 [0, 1], 5 [0, 0]] 6 7g = [[0, 0], 8 [0, 0], 9 [0, 1], 10 [0, 1], 11 [0, 0]]
- For
i = 4
,j = 1
:- Again,
f[4][1]
becomes the sum off[3][1]
andg[3][1]
, totaling to2
. g[4][1]
carries overg[3][1]
and addsf[3][0]
.
- Again,
Tables now:
1f = [[0, 0], 2 [1, 0], 3 [0, 1], 4 [0, 1], 5 [0, 2]] 6 7g = [[0, 0], 8 [0, 0], 9 [0, 1], 10 [0, 1], 11 [0, 1]]
Finally, we return the sum of f[n][k]
and g[n][k]
, which is f[4][1] + g[4][1] = 2 + 1 = 3
modulo 10^9 + 7
, so the result is 3
.
So, for n = 4
and k = 1
, there are 3
distinct ways we can draw 1
line segment that covers at least two points on the 1-D plane, without overlap, and with the possibility of shared endpoints.
Solution Implementation
1class Solution:
2 def numberOfSets(self, n: int, k: int) -> int:
3 # Define the modulus for large numbers to prevent overflow.
4 MOD = 10**9 + 7
5
6 # Create two 2D lists (tables) for dynamic programming.
7 # 'dp' tracks the number of sets that can be formed using the first 'i' points with 'j' segments including the ith point.
8 # 'cumulative' tracks the cumulative count of sets including previous points.
9 dp = [[0] * (k + 1) for _ in range(n + 1)]
10 cumulative = [[0] * (k + 1) for _ in range(n + 1)]
11
12 # Initialize the base case: 1 way to form 0 segments using 1 point.
13 dp[1][0] = 1
14
15 # Fill the dynamic programming tables.
16 for i in range(2, n + 1): # For each point from 2 to n
17 for j in range(k + 1): # For each number of segments from 0 to k
18 # The number of ways to form 'j' segments considering 'i' as the last point
19 # is equal to the sum of the previous point without the ith point and the cumulative count.
20 dp[i][j] = (dp[i - 1][j] + cumulative[i - 1][j]) % MOD
21
22 # The cumulative count up to 'i' for 'j' segments is the same as the previous cumulative count.
23 cumulative[i][j] = cumulative[i - 1][j]
24
25 # If there is at least one segment to place,
26 if j:
27 # Add the number of ways to form 'j-1' segments not including the ith point.
28 cumulative[i][j] += dp[i - 1][j - 1]
29 cumulative[i][j] %= MOD
30 # Add the number of ways to form 'j-1' segments including previous points.
31 cumulative[i][j] += cumulative[i - 1][j - 1]
32 cumulative[i][j] %= MOD
33
34 # The final answer is the sum of the ways to form 'k' segments including the nth point and not including the nth point.
35 return (dp[-1][-1] + cumulative[-1][-1]) % MOD
36
1class Solution {
2 private static final int MOD = (int) 1e9 + 7; // Defining the modulus value for large numbers to prevent overflow
3
4 public int numberOfSets(int n, int k) {
5 int[][] dpEnd = new int[n + 1][k + 1]; // dpEnd[i][j] represents the number of ways to form j segments with i points, with a segment ending at point i
6 int[][] dpNotEnd = new int[n + 1][k + 1]; // dpNotEnd[i][j] represents the number of ways to form j segments with i points, without a segment ending at point i
7
8 dpEnd[1][0] = 1; // Base case: There is 1 way to form 0 segments with 1 point
9
10 // Iterate over the number of points
11 for (int i = 2; i <= n; ++i) {
12 // Iterate over the number of segments
13 for (int j = 0; j <= k; ++j) {
14 // The number of ways with a segment ending at the current point i is equal to the sum of the number of ways
15 // with and without a segment ending at the previous point (i-1), for the same number of segments
16 dpEnd[i][j] = (dpEnd[i - 1][j] + dpNotEnd[i - 1][j]) % MOD;
17
18 // For the number of ways without a segment ending at the current point i carry over the number
19 // from the previous point i-1 without a segment ending
20 dpNotEnd[i][j] = dpNotEnd[i - 1][j];
21
22 // If we can form at least one segment
23 if (j > 0) {
24 // There are two ways to extend the number of ways to form j segments without a segment ending at point i:
25 // 1) Use the number of ways to form j-1 segments with a segment ending at point i-1, and
26 // start a new segment at point i-1 extending to i.
27 // 2) Extend the number of ways to form j segments without a segment ending at point i-1 by adding a point i.
28 dpNotEnd[i][j] += (dpEnd[i - 1][j - 1] + dpNotEnd[i - 1][j - 1]) % MOD;
29 // Modulo operation to prevent overflow
30 dpNotEnd[i][j] %= MOD;
31 }
32 }
33 }
34
35 // The total number of ways to form k segments with n points is the sum of the ways with and without a segment ending at point n
36 return (dpEnd[n][k] + dpNotEnd[n][k]) % MOD;
37 }
38}
39
1class Solution {
2public:
3 int dpSegmentEnd[1010][1010]; // dp array for cases where a segment ends at a point
4 int dpNoSegmentEnd[1010][1010]; // dp array for cases with no segment ending at a point
5 const int MOD = 1e9 + 7; // Define the modulo operator value
6
7 // Method that calculates the number of ways to divide a line into k non-overlapping line segments
8 int numberOfSets(int n, int k) {
9 // Initialize dp arrays
10 memset(dpSegmentEnd, 0, sizeof(dpSegmentEnd));
11 memset(dpNoSegmentEnd, 0, sizeof(dpNoSegmentEnd));
12 dpSegmentEnd[1][0] = 1; // Base case: only one way when there is one point and no segments
13
14 // Dynamic programming iterations
15 for (int i = 2; i <= n; ++i) { // Iterate over points
16 for (int j = 0; j <= k; ++j) { // Iterate over number of segments
17 // Ways where a segment does not end at the current point
18 dpSegmentEnd[i][j] = (dpSegmentEnd[i - 1][j] + dpNoSegmentEnd[i - 1][j]) % MOD;
19
20 // Ways where a segment ends at the current point
21 dpNoSegmentEnd[i][j] = dpNoSegmentEnd[i - 1][j];
22
23 if (j > 0) {
24 // If it is possible to add a new segment, update the ways count for segments ending at current point
25 dpNoSegmentEnd[i][j] = (dpNoSegmentEnd[i][j] + dpSegmentEnd[i - 1][j - 1]) % MOD;
26 dpNoSegmentEnd[i][j] = (dpNoSegmentEnd[i][j] + dpNoSegmentEnd[i - 1][j - 1]) % MOD;
27 }
28 }
29 }
30 // Total number of ways is the sum of ways where last segment ends on point n and where it doesn't
31 return (dpSegmentEnd[n][k] + dpNoSegmentEnd[n][k]) % MOD;
32 }
33};
34
1// A function that calculates the number of ways to divide a line into `k` non-overlapping segments.
2function numberOfSets(n: number, k: number): number {
3 // Create a 2D array `f` where `f[i][j]` represents the number of ways to draw `j` segments with `i` points,
4 // ending with a point.
5 const f = Array.from({ length: n + 1 }, () => new Array(k + 1).fill(0));
6 // Create a 2D array `g` where `g[i][j]` represents the number of ways to draw `j` segments with `i` points,
7 // possibly ending with a segment.
8 const g = Array.from({ length: n + 1 }, () => new Array(k + 1).fill(0));
9 // Base case: there's one way to draw 0 segments with 1 point.
10 f[1][0] = 1;
11 // The modulo value for preventing integer overflow.
12 const mod = 10 ** 9 + 7;
13
14 // Loop through the points.
15 for (let i = 2; i <= n; ++i) {
16 // Loop through the number of segments.
17 for (let j = 0; j <= k; ++j) {
18 // Number of ways to draw `j` segments up to point `i`, ending with a point.
19 f[i][j] = (f[i - 1][j] + g[i - 1][j]) % mod;
20
21 // Number of ways to draw `j` segments up to point `i`, possibly ending with a segment (continuing).
22 g[i][j] = g[i - 1][j];
23
24 // If we have at least one segment.
25 if (j) {
26 // Add ways to draw `j-1` segments up to point `i-1`, then add a new segment ending at point `i`.
27 g[i][j] += f[i - 1][j - 1];
28 g[i][j] %= mod;
29
30 // Add ways to continue the segment from `j-1` segments up to point `i-1`.
31 g[i][j] += g[i - 1][j - 1];
32 g[i][j] %= mod;
33 }
34 }
35 }
36
37 // Return the number of ways to draw `k` segments with `n` points, which could either end with a point or a segment.
38 return (f[n][k] + g[n][k]) % mod;
39}
40
Time and Space Complexity
The given Python code defines a class Solution
with a method numberOfSets
that calculates the number of ways to draw k
non-overlapping line segments from n
distinct points. The dynamic programming approach is used with two 2D lists (or matrices if you prefer), f
and g
. Here's an analysis of the time and space complexity of the code:
Time Complexity
The code consists of nested loops: the outer loop runs for n - 1
iterations (starting from 2 up to n
), and the inner loop runs for k + 1
iterations (starting from 0 up to k
). Since each iteration performs a constant number of operations including assignments and modular additions, the time complexity is a direct product of the number of iterations of these loops.
Therefore, the time complexity is O(n * k)
.
Space Complexity
Two matrices f
and g
are created, each of size (n + 1) x (k + 1)
. No additional space that grows with n
or k
is used in the algorithm, so the space complexity is determined by the size of these matrices.
Thus, the space complexity is O(n * k)
since it's proportional to the amount of space used to store the matrices.
Learn more about how to find time and space complexity quickly using problem constraints.
Depth first search is equivalent to which of the tree traversal order?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we