#1621

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Number of Sets of K Non-Overlapping Line Segments

Count all valid arrangements of k non-overlapping line segments on n points using state transition dynamic programming.

Problem Statement

Given n points labeled from 0 to n-1 on a 1-D plane, compute how many ways k non-overlapping line segments can be drawn. Each segment must cover at least two points, and endpoints are integers. Segments can share endpoints, but cannot overlap otherwise.

Return the total number of valid arrangements modulo 10^9 + 7. For example, with n = 4 and k = 2, there are 5 valid segment sets: {(0,2),(2,3)}, {(0,1),(1,3)}, {(0,1),(2,3)}, {(1,2),(2,3)}, {(0,1),(1,2)}. Constraints are 2 <= n <= 1000 and 1 <= k <= n-1.

Examples

Example 1

Input: n = 4, k = 2

Output: 5

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

The 3 ways are {(0,1)}, {(0,2)}, {(1,2)}.

Example 3

Input: n = 30, k = 7

Output: 796297179

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 <= 1000
1 <= k <= n-1

Solution Approach

Dynamic Programming with State Transition

Define dp[i][j] as the number of ways to draw j segments using the first i points. Transition by either skipping the current point or ending a segment at the current point. This captures all valid segment placements without overlap and allows incremental computation.

Combinatorial Optimization

Recognize that choosing segment endpoints is similar to combinations with repetition under constraints. Precompute factorials and inverse factorials modulo 10^9 + 7 to efficiently calculate the number of ways segments can be distributed among points while respecting non-overlap.

Space Optimization

Since dp[i][j] depends only on previous point states, reduce space complexity to O(k) by using rolling arrays. This allows handling large n efficiently while preserving correctness of the state transition counts.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n*k) for the DP approach, as each dp state is computed once. Space can be reduced to O(k) using rolling arrays. Precomputation for combinatorial formulas takes O(n+k) time and space.

What Interviewers Usually Probe

Focus on defining states that include the current index and remaining segments to form.
Expect discussion about modulo arithmetic and integer overflows.
Look for optimization from O(n*k) space to O(k) using rolling DP arrays.

Common Pitfalls or Variants

Common pitfalls

Incorrectly allowing overlapping segments by not enforcing endpoint constraints.
Forgetting that segments must cover at least two points, causing overcounting.
Neglecting modulo operations, leading to incorrect results for large n and k.

Follow-up variants

Count the number of non-overlapping segments covering all n points.
Allow segments of length exactly 2 and count the arrangements for k segments.
Compute the number of sets where segments can only share start points, not end points.

FAQ

What is the key pattern in Number of Sets of K Non-Overlapping Line Segments?

The main pattern is state transition dynamic programming where each state tracks the current index and remaining segments to draw.

Why do we need modulo 10^9 + 7?

Because the total number of segment arrangements grows rapidly with n and k, modulo ensures the result fits in standard integer types.

Can we solve this problem with only combinatorics?

Yes, but direct combinatorial formulas can be inefficient or require careful handling of overlapping endpoints, making DP more practical for large n.

How do we handle segments sharing endpoints?

The DP formulation allows segments to share endpoints naturally, but enforces that no two segments overlap beyond shared endpoints.

What are common mistakes when implementing the DP?

Typical errors include counting segments of length 1, failing to update previous dp states correctly, or neglecting modulo operations leading to overflow.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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]) % mod

Continue Practicing

#1641 count sorted vowel strings #1643 kth smallest instructions #1569 number of ways to reorder array to get same bst