Skip to main content
Talentd

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

MediumMathDynamic ProgrammingCombinatorics9 min readAsked at: Amazon
Practice this problem

Problem Statement

Given n points on a 1-D plane, where the ith point (from 0 to n-1) is at x = i, find the number of ways we can draw exactly k non-overlapping line segments such that each segment covers two or more points. The endpoints of each segment must have integral coordinates. The k line segments do not have to cover all n points, and they are allowed to share endpoints.

Return the number of ways we can draw k non-overlapping line segments. Since this number can be huge, return it modulo 109 + 7.

 

Example 1:

Input: n = 4, k = 2
Output: 5
Explanation: 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
Explanation: The 3 ways are {(0,1)}, {(0,2)}, {(1,2)}.

Example 3:

Input: n = 30, k = 7
Output: 796297179
Explanation: 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

Approach Overview

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.

Approach 1: Dynamic Programming Approach

This approach employs a dynamic programming technique to count the ways to form non-overlapping line segments. Define a DP table where dp[i][j] represents the number of ways to form j segments using the first i points. Base cases are when j = 0 or i < 2j.

The solution uses a dynamic programming table dp where dp[i][j] denotes the number of ways to form j non-overlapping segments with the first i points. For segment formation, binomial coefficients are used to choose the pairs of points to start segments.

Code

PythonC

Python

C

Complexity

Time Complexity: O(n^2 * k), Space Complexity: O(n^2).

Try this approach in the editor →

Approach 2: Mathematical Combinatorics with Prefix Sums

This approach leverages combinatorics and prefix sums to optimize segment counting. The main idea is to precompute binomial coefficients and use prefix sums to quickly calculate the number of ways to choose end points for segments.

The Java solution utilizes a two-dimensional array dp where dp[i][j] stores the number of ways to form j segments ending at point i. The prefix sum helps ensure all possible combinations are efficiently considered for each ending point.

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O(n^2), Space Complexity: O(n^2).

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(n^2 * k), Space Complexity: O(n^2).

Mathematical Combinatorics with Prefix Sums

Time Complexity: O(n^2), Space Complexity: O(n^2).

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with Prefix SumsO(nk)O(nk)Standard interview solution when deriving states and transitions step by step
Mathematical Combinatorics (Binomial Coefficient)O(nk) preprocessing, O(1) resultO(nk)Best when you recognize the combinatorial pattern and want a direct counting formula

Video Solution

1621. Number of Sets of K Non-Overlapping Line Segments | Leetcode biweekly contest 37 | LEETCODE • code Explainer • 2,721 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Number of Sets of K Non-Overlapping Line Segments easy or hard?
This problem is rated Medium because the constraints are simple but the counting logic is not immediately obvious. Recognizing the DP state transitions or the combinatorial identity C(n + k - 1, 2k) requires solid experience with dynamic programming and combinatorics.
Number of Sets of K Non-Overlapping Line Segments Python/Java solution
Python, Java, C, and JavaScript implementations typically follow the same DP recurrence with modulo arithmetic. The code maintains a dp array and prefix sums to update states efficiently in O(nk) time.
How to solve Number of Sets of K Non-Overlapping Line Segments in O(nk)?
Use a DP table where dp[i][j] counts ways using the first i points. At each point, either extend configurations without ending a segment or finish a segment at that point. Prefix sums accumulate all valid previous states so each transition becomes constant time, resulting in O(nk) total complexity.
What is the best approach for Number of Sets of K Non-Overlapping Line Segments?
Dynamic programming with prefix sums is the most common approach. Define dp[i][j] as the number of ways to create j segments using the first i points and use prefix sums to efficiently add all valid starting positions. This reduces transitions to O(1) and yields overall O(nk) time and O(nk) space complexity.
Is Number of Sets of K Non-Overlapping Line Segments asked at Google/Amazon/Meta?
Interval counting and combinatorics DP problems like this frequently appear in interviews at companies such as Google, Amazon, and Meta. They test dynamic programming design, prefix sum optimization, and the ability to convert interval constraints into counting formulas.
What data structure is used in Number of Sets of K Non-Overlapping Line Segments?
The core structure is a 2D dynamic programming table combined with prefix sums for fast aggregation. The combinatorial approach additionally relies on binomial coefficient tables built using Pascal’s triangle or modular arithmetic.
What is the time complexity of Number of Sets of K Non-Overlapping Line Segments?
The typical dynamic programming solution runs in O(nk) time with O(nk) space. Each DP state represents using i points and forming j segments, and prefix sums remove the need for nested loops over previous start positions.

Ready to solve this problem?

Practice Number of Sets of K Non-Overlapping Line Segments with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer