Number of Sets of K Non-Overlapping Line Segments - Solution & Explanation

Problem Overview: You are given n points on a line labeled 0 to n-1. The task is to count how many ways you can draw exactly k line segments such that each segment uses two different points and no two segments overlap. Segments can share endpoints but cannot overlap in their interior.

Approach 1: Dynamic Programming (O(nk) time, O(nk) space)

This approach models the problem using dynamic programming. Define dp[i][j] as the number of ways to form j non‑overlapping segments using the first i points. When processing a new point, you either skip it or end a segment at that point. A prefix sum helps accumulate all valid starting points for segments that end at i. The transition effectively sums all configurations where the previous segment ended before the current one starts. This builds the answer iteratively while applying modulo arithmetic.

The key insight: every segment contributes a start and end point, but you must ensure the end index is greater than the start and that previous segments don't overlap. Prefix sums reduce the inner summation so each state update stays constant time.

Approach 2: Mathematical Combinatorics with Prefix Sums (O(nk) preprocessing or O(1) query, O(nk) space)

The structure of valid segments reveals a combinatorics pattern. Each segment selects two ordered endpoints while maintaining a global ordering that prevents overlap. This arrangement can be transformed into choosing positions for 2k endpoints among an expanded sequence of points and gaps. The number of valid configurations becomes a binomial coefficient: C(n + k - 1, 2k).

To compute this efficiently under modulo constraints, precompute combinations using Pascal’s triangle or prefix-based DP. This avoids factorial division issues and keeps computation stable for large n. Once the combination table is built, retrieving the final answer is constant time.

This method reframes the problem from simulation to counting arrangements. Instead of iterating over possible segment placements, it directly counts valid endpoint selections using combinatorial identities.

Recommended for interviews: The dynamic programming solution is typically expected. It demonstrates control over state design, prefix sums, and transition optimization—core math and DP reasoning used in many interval problems. Mentioning the combinatorial formula shows deeper insight and can turn the problem into a quick calculation once you recognize the pattern.