Number of Sets of K Non-Overlapping Line Segments — Solution
Number of Sets of K Non-Overlapping Line Segments solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Number of Sets of K Non-Overlapping Line Segments is a medium coding problem on dynamic programming, math and combinatorics, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Dynamic Programming, Math, Combinatorics
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are n points on a line at positions x = 0, 1, …, n - 1. Draw exactly k segments such that:
- each segment starts and ends at one of the points and covers at least two points (its length is at least 1);
- no two segments overlap, although they may share an endpoint;
- the segments do not have to cover every point.
Return the number of different ways to draw them, modulo 10^9 + 7.
Example 1
Input: n = 4, k = 2
Output: 5
Explanation: {(0,2),(2,3)}, {(0,1),(1,3)}, {(0,1),(2,3)}, {(1,2),(2,3)} and {(0,1),(1,2)}.
Example 2
Input: n = 3, k = 1
Output: 3
Explanation: {(0,1)}, {(0,2)} and {(1,2)}.
Example 3
Input: n = 30, k = 7
Output: 796297179
Explanation: The exact count is 3,796,297,200; modulo 10^9 + 7 it is 796,297,179.
Constraints
2 <= n <= 10001 <= k <= n - 1
Hints for Number of Sets of K Non-Overlapping Line Segments
Hint 1
A DP works: let
f(i, j)be the number of ways to placejsegments among the firsti + 1points, and decide whether a segment ends at pointi. With prefix sums this is O(n·k).Hint 2
There is a neater view. Shared endpoints are the only obstacle to a plain 'choose 2k endpoints' count. What if you stretched each segment by one unit?
Hint 3
Add
k - 1extra points so that segments sharing an endpoint get separate ones: the configurations become choices of2kdistinct points out ofn + k - 1, so the answer isC(n + k - 1, 2k).
How to solve Number of Sets of K Non-Overlapping Line Segments
The answer is the binomial coefficient C(n + k − 1, 2k): giving every segment except the last one an extra unit of length turns 'non-overlapping, possibly touching' into '2k distinct, strictly increasing endpoints'.
Approach
- Let
m = n + k - 1andr = 2k. - Compute
m · (m−1) · … · (m−r+1)andr!modulop = 10^9 + 7. - Return the first product times the modular inverse of the second (Fermat:
r!^(p−2) mod p).
Why it works
List the endpoints in order: l1 < r1 <= l2 < r2 <= … <= lk < rk, all in 0..n−1. Shift the i-th segment's endpoints right by i − 1 (so l_i' = l_i + i − 1, r_i' = r_i + i − 1). Then every <= becomes a strict <, the values range over 0..n+k−2, and the map is reversible. So the sets of segments are exactly the 2k-element subsets of n + k − 1 points, read off in sorted order.
Complexity
- Time —
O(k + log p) - Space —
O(1)
Pitfalls
- Products of two residues below 10^9 + 7 overflow 32 bits (and lose precision in a JavaScript double) — multiply in 64-bit or split the multiplication.
- The obvious DP is O(n²·k) without prefix sums — too slow at n = 1000.
- Forgetting that touching segments are allowed gives
C(n, 2k), which undercounts.
Reference solution
Python
def numberOfSets(n: int, k: int) -> int:
MOD = 10 ** 9 + 7
m, r = n + k - 1, 2 * k
num = 1
den = 1
for i in range(r):
num = num * (m - i) % MOD
den = den * (i + 1) % MOD
return num * pow(den, MOD - 2, MOD) % MODJava
public static int numberOfSets(int n, int k) {
final long MOD = 1000000007L;
long m = n + k - 1, r = 2L * k;
long num = 1, den = 1;
for (long i = 0; i < r; i++) {
num = num * (m - i) % MOD;
den = den * (i + 1) % MOD;
}
long inv = 1, base = den, e = MOD - 2;
while (e > 0) {
if ((e & 1) == 1) inv = inv * base % MOD;
base = base * base % MOD;
e >>= 1;
}
return (int) (num * inv % MOD);
}C++
int numberOfSets(int n, int k) {
const long long MOD = 1000000007LL;
long long m = n + k - 1, r = 2LL * k;
long long num = 1, den = 1;
for (long long i = 0; i < r; i++) {
num = num * (m - i) % MOD;
den = den * (i + 1) % MOD;
}
long long inv = 1, base = den, e = MOD - 2;
while (e > 0) {
if (e & 1) inv = inv * base % MOD;
base = base * base % MOD;
e >>= 1;
}
return (int)(num * inv % MOD);
}JavaScript
var numberOfSets = function(n, k) {
var MOD = 1000000007;
var mul = function(a, b) {
return ((a * (b >>> 16)) % MOD * 65536 + a * (b & 65535)) % MOD;
};
var power = function(base, e) {
var result = 1;
while (e > 0) {
if (e % 2 === 1) result = mul(result, base);
base = mul(base, base);
e = Math.floor(e / 2);
}
return result;
};
var m = n + k - 1, r = 2 * k;
var num = 1, den = 1;
for (var i = 0; i < r; i++) {
num = mul(num, m - i);
den = mul(den, i + 1);
}
return mul(num, power(den, MOD - 2));
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming