Practice Number of Sets of K Non-Overlapping Line Segments
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Number of Sets of K Non-Overlapping Line Segments
Problem Statement
Points lie at integer coordinates 0 through n - 1. Choose exactly k line segments with endpoints among those points. Every segment must have positive length. Their interiors cannot overlap, but neighboring segments may share an endpoint, and unused points are allowed. Return the number of different sets modulo 1,000,000,007. Approach: Keep shared endpoints distinct from overlapping interiors when counting. A combinatorial formulation gives C(n + k - 1, 2k); compute it with modular arithmetic rather than floating-point factorials. A prefix-based dynamic program is another option when explaining how a new segment extends a smaller set.
Source: Number of Sets of K Non-Overlapping Line Segments on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
n = 5, k = 2
15
Counting endpoint choices while allowing adjacent segments to share an endpoint gives C(6,4) = 15.
# Example 2
n = 3, k = 2
1
The only set is the segment from 0 to 1 together with the segment from 1 to 2.
Constraints
How to solve Number of Sets of K Non-Overlapping Line Segments
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
Adjacent segments may share an endpoint; giving every potential shared point a duplicate by inserting k - 1 virtual points turns each valid set into a plain choice of 2k distinct positions out of n + k - 1, which is why the count is a single binomial coefficient.
Why brute force is not enough
A dynamic program that tries every start and end for each new segment runs in O(n^2 k), near 10^9 for n up to 1000 and k up to 999; explicit enumeration of sets is exponential.
Approach
- Label positions 0 through n + k - 2 on a virtual line and choose any 2k of them, sorted as p1 < p2 < ... < p2k.
- Map the j-th segment to the real interval from p(2j-1) - (j - 1) to p(2j) - (j - 1); subtracting j - 1 removes the virtual gaps before it, so its left end lands at or after the previous right end and all endpoints stay within 0 to n - 1.
- Distinct virtual positions guarantee positive length and disjoint interiors, and a shared real endpoint corresponds exactly to two consecutive virtual positions, so the map is a bijection and the answer is C(n + k - 1, 2k).
- Compute the binomial modulo 10^9 + 7 with factorials and modular inverses via Fermat's little theorem; if asked for the dynamic program instead, keep two states per point (no open segment, or a segment passing through) and allow a segment closing at a point to reopen there.
Walkthrough of Example 1
n = 5, k = 2 → 15
- n + k - 1 = 6 virtual positions 0 through 5, and 2k = 4 of them must be chosen.
- {0,1,2,3} maps to [0,1] and [1,2], sharing point 1; {0,1,3,4} maps to [0,1] and [2,3]; {0,2,3,5} maps to [0,2] and [2,4].
- Each 4-subset yields a distinct valid set and every valid set arises this way, so the count is C(6,4).
- C(6,4) = 720 / (24 * 2) = 15, below the modulus, so the answer is 15.
Time and space
Time O(n + k) · Space O(n + k). n is the number of points and k the segment count; factorial and inverse-factorial tables up to n + k - 1 are built once and the binomial takes a few modular multiplications.
Interview pitfalls
- Choosing 2k points directly out of n, which forbids shared endpoints; for n = 5 and k = 2 that gives C(5,4) = 5 instead of 15.
- Dividing by factorials with integer or floating-point arithmetic instead of modular inverses; overflow and rounding both corrupt the result.
- Using n + k virtual positions instead of n + k - 1.
- In the dynamic-programming alternative, omitting the transition that closes a segment and immediately opens a new one at the same point.
Follow-up questions interviewers ask
- How would you count sets where segments may not even touch at endpoints?
- What if every segment must have length at least L?
Further reading on the technique: Binomial coefficient
Related LeetCode Problems
Practice more problems similar to Number of Sets of K Non-Overlapping Line Segments.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.