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.

Description Hints 2 Solution Video 15:52

1621. Number of Sets of K Non-Overlapping Line Segments

Medium69.3% acceptance1 company

Given n points on a 1-D plane, where the i^th 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 10⁹ + 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 10⁹ + 7 gives us 796297179.

Constraints:

2 <= n <= 1000
1 <= k <= n-1

Asked at 1 company

Amazon

Topics

Hints open one at a time

Hint 1

Try to use dynamic programming where the current index and remaining number of line segments to form can describe any intermediate state.

Hint 2

To make the computation of each state in constant time, we could add another flag to the state that indicates whether or not we are in the middle of placing a line (placed start point but no endpoint).

15:52

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def numberOfSets(self, n: int, k: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

4
2

Input

3
1

Input

30
7

Your code is saved on this device.Solution