Number of Sets of K Non-Overlapping Line Segments

Number of Sets of K Non-Overlapping Line Segments - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: n = 4, k = 2

› Output: 3

💡 Note: With 4 points (0,1,2,3), we can draw 2 non-overlapping segments in 3 ways: [0,1]+[2,3], [0,2]+skip 1 point+[3,3], and [1,3]+skip middle points. Wait, segments must cover 2+ points, so [3,3] is invalid. The valid ways are: segments covering [0,1] and [2,3], segments covering [0,2] and skip, actually this needs more careful analysis.

Example 2 — Minimum Case

$ Input: n = 3, k = 1

› Output: 3

💡 Note: With 3 points, we can draw 1 segment in 3 ways: [0,1], [0,2], or [1,2]. Each covers at least 2 points.

Example 3 — Impossible Case

$ Input: n = 3, k = 2

› Output: 0

💡 Note: With only 3 points, we cannot draw 2 non-overlapping segments where each covers at least 2 points.

Constraints

2 ≤ n ≤ 1000
1 ≤ k ≤ n/2

Visualization

Tap to expand

Understanding the Visualization

Input

n=4 points on line, need k=2 segments

Process

Find all ways to place 2 non-overlapping segments

Output

Count = 3 valid arrangements

Key Takeaway

🎯 Key Insight: Transform to combinatorial problem of placing non-overlapping intervals optimally

Asked in

G Google 15 M Microsoft 12 a Amazon 8

This problem uses dynamic programming to count ways to place k non-overlapping line segments. The key insight is that this reduces to a combinatorial problem that can be solved with DP in O(n²k) time or with mathematical formulas in O(k) time.

Common Approaches

Approach	Time	Space	Notes
✓ Memoized Dynamic Programming	O(n²k)	O(nk)	Cache recursive results to avoid redundant calculations
Bottom-Up Dynamic Programming	O(n²k)	O(nk)	Build solution iteratively using 2D DP table
Mathematical Formula (Combinatorics)	O(k)	O(1)	Direct combinatorial formula using binomial coefficients
Recursive Brute Force	O(2^n)	O(n)	Try all possible ways to place k line segments recursively

Memoized Dynamic Programming — Algorithm Steps

Use recursive function with memoization
Cache results for each (position, segments_left) state
Return cached result if state already computed

Visualization

Tap to expand

Step-by-Step Walkthrough

Compute

Calculate result for new state (pos=1, k=1)

Cache

Store result in memo table

Reuse

Return cached result when same state appears again

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const int MOD = 1000000007;
const int MAXN = 1005;
int memo[MAXN][MAXN];
int visited[MAXN][MAXN];

int countWays(int pos, int segmentsLeft, int n) {
    if (segmentsLeft == 0) {
        return 1;
    }
    if (pos >= n) {
        return 0;
    }
    
    if (visited[pos][segmentsLeft]) {
        return memo[pos][segmentsLeft];
    }
    
    long long total = 0;
    // Don't place segment starting at pos
    total += countWays(pos + 1, segmentsLeft, n);
    
    // Place segment starting at pos
    for (int end = pos + 1; end < n; end++) {
        total += countWays(end + 1, segmentsLeft - 1, n);
    }
    
    visited[pos][segmentsLeft] = 1;
    memo[pos][segmentsLeft] = total % MOD;
    return memo[pos][segmentsLeft];
}

int solution(int n, int k) {
    memset(visited, 0, sizeof(visited));
    return countWays(0, k, n);
}

int main() {
    int n, k;
    scanf("%d", &n);
    scanf("%d", &k);
    printf("%d\n", solution(n, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²k)

Each of n*k states computed once, each taking O(n) time to compute

⚠ Quadratic Growth

Space Complexity

O(nk)

Memoization table stores results for n*k different states

⚡ Linearithmic Space

23.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoized Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler