Number of Sets of K Non-Overlapping Line Segments: DP on Segments

You are given n points on a 1-D plane, labeled 0 through n - 1. You need to draw exactly k non-overlapping line segments, where each segment connects two distinct points. Segments can share endpoints but cannot overlap. Return the number of ways to draw these segments, modulo 10^9 + 7.

This is LeetCode 1621: Number of Sets of K Non-Overlapping Line Segments. For example, with n = 4 and k = 2, there are 5 valid configurations. With n = 3 and k = 1, there are 3: the segments [0,1], [1,2], and [0,2].

Why this problem matters

Placing non-overlapping segments on a line is a counting problem that blends combinatorics with DP. The tricky part is that segments can share endpoints. That rules out a naive "pick k non-adjacent pairs" approach and forces you to think carefully about what state your DP needs to carry.

This problem teaches the "open/closed" state tracking pattern. At each point on the line, you are either inside a segment or not. That binary flag, combined with the number of segments completed so far, gives you enough information to count every valid configuration. This same pattern shows up in job scheduling problems, interval partitioning, and any DP where you need to track whether you are currently building something.

The key insight

The DP state needs three dimensions: which point you are at, how many segments you have completed, and whether you are currently drawing a segment. That third dimension is the key. Without it, you cannot distinguish between "waiting to start a new segment" and "extending a segment in progress."

Think of it as a state machine. At each point, you are in one of two modes: idle (not drawing) or active (drawing). From idle, you can stay idle (skip the point) or start a new segment. From active, you can extend the current segment to the next point or end it here. When you end a segment, the completed count goes up by one and you transition to idle.

The solution

def number_of_sets(n, k):
    MOD = 10**9 + 7
    dp = [[[0, 0] for _ in range(k + 1)] for _ in range(n)]

    for i in range(n):
        dp[i][0][0] = 1

    for i in range(1, n):
        for j in range(1, k + 1):
            dp[i][j][0] = (dp[i - 1][j][0] + dp[i - 1][j][1]) % MOD
            dp[i][j][1] = (dp[i - 1][j][1] + dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1]) % MOD

    return (dp[n - 1][k][0] + dp[n - 1][k][1]) % MOD

The array dp[i][j][s] stores the number of ways to reach point i with j segments completed and state s (0 = not drawing, 1 = currently drawing).

Base case: dp[i][0][0] = 1 for every point. Before drawing any segment, there is exactly one way to be at any point with zero segments done and not currently drawing: you simply have not started yet.

Transition for dp[i][j][0] (at point i, j complete, not drawing): you arrived here either by skipping point i while idle (dp[i-1][j][0]) or by ending a segment at point i (dp[i-1][j][1]). Both contribute, so you add them.

Transition for dp[i][j][1] (at point i, j complete, currently drawing): you are drawing the (j+1)th segment. You got here by extending a segment already in progress (dp[i-1][j][1]) or by starting a new segment at point i. Starting a new segment means you were idle at i-1 with j-1 complete (dp[i-1][j-1][0]) or you had just ended the jth segment at i-1 (dp[i-1][j-1][1]). Note that the "just ended and immediately started" case is what allows shared endpoints.

The answer is dp[n-1][k][0] + dp[n-1][k][1]: the total ways to have exactly k segments by the last point, whether or not you are still drawing (a segment ending at the last point is valid).

Visual walkthrough

Let's trace through a small example. With n = 4 and k = 2:

After initialization, dp[i][0][0] = 1 for all points. Everything else is 0.

At point 1 (i = 1): dp[1][1][1] = dp[0][0][0] + dp[0][0][1] = 1 + 0 = 1. You can start a segment from point 0 to point 1. dp[1][1][0] = dp[0][1][0] + dp[0][1][1] = 0. No way to have a complete segment at point 1 while idle yet.

At point 2 (i = 2): dp[2][1][1] = dp[1][1][1] + dp[1][0][0] + dp[1][0][1] = 1 + 1 + 0 = 2. Two ways: extend the segment from [0,1] to [0,2], or start a new segment [1,2]. dp[2][1][0] = dp[1][1][0] + dp[1][1][1] = 0 + 1 = 1. One complete segment, not drawing: the segment [0,1] ended.

At point 3 (i = 3): dp[3][2][0] = dp[2][2][0] + dp[2][2][1] = 0 + 1 = 1. dp[3][2][1] = dp[2][2][1] + dp[2][1][0] + dp[2][1][1] = 1 + 1 + 2 = 4. The answer is dp[3][2][0] + dp[3][2][1] = 1 + 4 = 5.

Complexity analysis

The outer loop runs n times, the inner loop runs k times, and each cell does O(1) work. Space is O(n * k * 2), which simplifies to O(n * k). You can optimize to O(k) space by only keeping two rows, but the full table is clearer and sufficient for the constraints (n, k up to 1000).

The building blocks

1. Segment state DP

dp[i][j][0] = (dp[i - 1][j][0] + dp[i - 1][j][1]) % MOD
dp[i][j][1] = (dp[i - 1][j][1] + dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1]) % MOD

This is the open/closed state pattern. You carry a flag that says whether you are currently inside a structure (segment, interval, group) or not. The flag doubles the state space but makes transitions clean. You will see this same idea in problems like "paint houses with cooldown" or "buy and sell stock with transaction limits." Any time you need to track whether an ongoing action is in progress, add a binary dimension to your DP.

2. Modular arithmetic

MOD = 10**9 + 7
dp[i][j][0] = (dp[i - 1][j][0] + dp[i - 1][j][1]) % MOD

Every addition gets a % MOD to prevent overflow. In Python, integers grow arbitrarily, so this is about correctness (the problem asks for the result modulo 10^9 + 7), not about preventing overflow. In C++ or Java, you would also need it to avoid integer overflow. The pattern is simple: apply % MOD after every addition.

Edge cases

• k = 0: zero segments to draw. The answer is always 1 (there is exactly one way to do nothing). The base case handles this.
• n = 2, k = 1: only one possible segment, [0, 1]. Answer: 1.
• k >= n: if k >= n, you cannot fit k segments because each segment needs at least two points and they share at most endpoints. When 2 * k > n + k - 1, the answer is 0. The DP naturally returns 0 in this case since there are not enough points to build that many segments.
• Large n and k: with n = 1000 and k = 1000, the table is 1000 x 1001 x 2, which fits comfortably in memory. The modular arithmetic keeps values bounded.
• n = 1: a single point, no segment possible for any k >= 1. Answer: 0.

From understanding to recall

You now understand why the DP needs three dimensions, how the open/closed flag enables shared endpoints, and how the transitions count every valid configuration. But recognizing this pattern during an interview requires more than a single read-through. You need to remember that the third dimension is a binary flag for "currently drawing," that ending a segment feeds into the idle state with an incremented count, and that starting a new segment can happen right after ending one (enabling shared endpoints).

The open/closed state pattern is one of the reusable building blocks in the CodeBricks system. You practice it individually with spaced repetition until adding the binary dimension to a DP is automatic. This problem, along with stock trading with cooldown and paint houses, forms a family of segment-state DP problems. Drilling them together is the fastest way to lock in this pattern.

Related posts

• Unique Paths - Grid DP with state transitions at each cell
• Coin Change - Classic DP with counting combinations
• Climbing Stairs - DP building from base cases