Number of Sets of K Non-Overlapping Line Segments solution and explanation
9 more videos on this problem
1621. Number of Sets of K Non-Overlapping Line Segments | Leetcode biweekly contest 37 | LEETCODEcode Explainer · 15:52 · 2K views
花花酱 LeetCode 1621. Number of Sets of K Non-Overlapping Line Segments - 刷题找工作 EP363Hua Hua · 33:02 · 1K views
LeetCode 1621. Number of Sets of K Non-Overlapping Line SegmentsHappy Coding · 25:47 · 1K views
leetcode 1621 Number of Sets of K Non-Overlapping Line Segments explanationIke Feng · 14:57 · 886 views
1621. Number of Sets of K Non-Overlapping Line Segments (Leetcode Medium)Programming Live with Larry · 30:05 · 560 views
【每日一题】1621. Number of Sets of K Non-Overlapping Line Segments, 10/19/2020Huifeng Guan · 42:11 · 438 views
Leetcode 1621. Number of Sets of K Non-Overlapping Line SegmentsElite Code · 30:06 · 216 views
Number of Sets of K Non-Overlapping Line Segments | Javascript Solution | LeetcodeCode JS · 11:05 · 145 views
大壮刷题 - Leetcode 1621 Number of Sets of K Non-Overlapping Line Segments, Medium, DP, Recursion大壮刷题 · 8:02 · 88 views
LeetCode 1621: Number of Sets of K Non-Overlapping Line SegmentsAlitaCode · 28:44 · 6 views
The problem
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 <= 10001 <= 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.
def numberOfSets(n, k):
MOD = 10**9 + 7
dp = [[0] * (k+1) for _ in range(n+1)]
C = [[0] * (n+1) for _ in range(n+1)]
for i in range(n+1):
C[i][0] = 1
for j in range(1, i+1):
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD
for i in range(2, n+1):
dp[i][1] = i * (i-1) // 2 # base case
for j in range(2, k+1):
for i in range(2*j, n+1):
dp[i][j] = C[i-1][2*j-1]
for x in range(1, i):
dp[i][j] = (dp[i][j] - dp[x][j-1] * (i-x)) % MOD
return dp[n][k]#include <stdio.h>
#define MOD 1000000007
int numberOfSets(int n, int k) {
int dp[n+1][k+1];
int C[n+1][n+1];
for (int i = 0; i <= n; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++) {
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
}
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= k; j++) {
dp[i][j] = 0;
}
}
for (int i = 2; i <= n; i++) {
dp[i][1] = i * (i-1) / 2;
if (dp[i][1] >= MOD) dp[i][1] %= MOD;
}
for (int j = 2; j <= k; j++) {
for (int i = 2 * j; i <= n; i++) {
dp[i][j] = C[i-1][2*j-1];
for (int x = 1; x < i; x++) {
dp[i][j] = (dp[i][j] - dp[x][j-1] * (i-x) % MOD + MOD) % MOD;
}
}
}
return dp[n][k];
}
int main() {
int n = 4, k = 2;
printf("%d\n", numberOfSets(n, k)); // Output: 5
return 0;
}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.
Time Complexity: O(n^2 * k), Space Complexity: O(n^2).
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.
public class Solution {
private static final int MOD = 1000000007;
public int numberOfSets(int n, int k) {
int[][] C = new int[n+1][n+1];
for (int i = 0; i <= n; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++) {
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
}
}
int[][] dp = new int[n+1][k+1];
int[][] prefixSum = new int[n+1][k+1];
for (int i = 0; i < n; i++) {
dp[i][0] = 1;
prefixSum[i][0] = i + 1;
}
for (int j = 1; j <= k; j++) {
for (int i = 2 * j; i <= n; i++) {
dp[i][j] = prefixSum[i-2][j-1];
dp[i][j] = (long)dp[i][j] * (i - j + 1) % MOD;
prefixSum[i][j] = (prefixSum[i-1][j] + dp[i][j]) % MOD;
}
}
return dp[n][k];
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.numberOfSets(4, 2)); // Output: 5
}
}const numberOfSets = (n, k) => {
const MOD = 1000000007;
const C = Array.from(Array(n+1), () => Array(n+1).fill(0));
for (let i = 0; i <= n; i++) {
C[i][0] = 1;
for (let j = 1; j <= i; j++) {
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
}
}
const dp = Array.from(Array(n+1), () => Array(k+1).fill(0));
const prefixSum = Array.from(Array(n+1), () => Array(k+1).fill(0));
for (let i = 0; i <= n; i++) {
dp[i][0] = 1;
prefixSum[i][0] = i + 1;
}
for (let j = 1; j <= k; j++) {
for (let i = 2 * j; i <= n; i++) {
dp[i][j] = prefixSum[i-2][j-1];
dp[i][j] = (dp[i][j] * (i - j + 1)) % MOD;
prefixSum[i][j] = (prefixSum[i-1][j] + dp[i][j]) % MOD;
}
}
return dp[n][k];
};
console.log(numberOfSets(4, 2)); // Output: 5The 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.
Time Complexity: O(n^2), Space Complexity: O(n^2).
Approach 3: Default Approach
class Solution {
public:
int f[1010][1010];
int g[1010][1010];
const int mod = 1e9 + 7;
int numberOfSets(int n, int k) {
memset(f, 0, sizeof(f));
memset(g, 0, sizeof(g));
f[1][0] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 0; j <= k; ++j) {
f[i][j] = (f[i - 1][j] + g[i - 1][j]) % mod;
g[i][j] = g[i - 1][j];
if (j > 0) {
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[n][k] + g[n][k]) % mod;
}
};function numberOfSets(n: number, k: number): number {
const f = Array.from({ length: n + 1 }, _ => new Array(k + 1).fill(0));
const g = Array.from({ length: n + 1 }, _ => new Array(k + 1).fill(0));
f[1][0] = 1;
const mod = 10 ** 9 + 7;
for (let i = 2; i <= n; ++i) {
for (let j = 0; j <= k; ++j) {
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[n][k] + g[n][k]) % mod;
}func numberOfSets(n int, k int) int {
f := make([][]int, n+1)
g := make([][]int, n+1)
for i := range f {
f[i] = make([]int, k+1)
g[i] = make([]int, k+1)
}
f[1][0] = 1
var mod int = 1e9 + 7
for i := 2; i <= n; i++ {
for j := 0; j <= k; j++ {
f[i][j] = (f[i-1][j] + g[i-1][j]) % mod
g[i][j] = g[i-1][j]
if j > 0 {
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[n][k] + g[n][k]) % mod
}Complexity comparison
| Approach | Complexity |
|---|---|
| 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 | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Prefix Sums | O(nk) | O(nk) | Standard interview solution when deriving states and transitions step by step |
| Mathematical Combinatorics (Binomial Coefficient) | O(nk) preprocessing, O(1) result | O(nk) | Best when you recognize the combinatorial pattern and want a direct counting formula |
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.