Number of Sets of K Non-Overlapping Line Segments

Medium
1296.

Number of Sets of K Non-Overlapping Line Segments

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.

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 <= 1000
  • 1 <= k <= n - 1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var numberOfSets = function(n, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 1000
  • 1 <= k <= n - 1

Hints for Number of Sets of K Non-Overlapping Line Segments

  1. Hint 1

    A DP works: let f(i, j) be the number of ways to place j segments among the first i + 1 points, and decide whether a segment ends at point i. With prefix sums this is O(n·k).

  2. 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?

  3. Hint 3

    Add k - 1 extra points so that segments sharing an endpoint get separate ones: the configurations become choices of 2k distinct points out of n + k - 1, so the answer is C(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

  1. Let m = n + k - 1 and r = 2k.
  2. Compute m · (m−1) · … · (m−r+1) and r! modulo p = 10^9 + 7.
  3. 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) % MOD

Java

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