LeetCode Entry

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

16.09.2026 medium 2026 kotlin rust

Ways to peek K intervals from N points

1621. Number of Sets of K Non-Overlapping Line Segments medium substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1484

Problem TLDR

Ways to peek K intervals from N points

Intuition

DFS DP: choose between continue, stop, start and stop-start Math combinatorics: each interval is two points, meaning we are choosing 2k points all at once from n+k-1 total possible points nCr (n+k-1 2k)

Approach

• 1D dp solution is row-by-row Pascal’s Triangle

Complexity

• Time complexity: \(O(nk)\)

• Space complexity: \(O(n)\)

Code

    fun numberOfSets(n: Int, k: Int): Int {
        var num = 1L; var den = 1L; val M = 1_000_000_007L
        for (i in 1..2 * k) { num = num * (n + k - i) % M; den = den * i % M }
        return (num * den.toBigInteger().modInverse(M.toBigInteger()).toLong() % M).toInt()
    }

    pub fn number_of_sets(n: i32, k: i32) -> i32 {
        let mut dp = vec![0; 2 * k as usize + 1]; dp[0] = 1;
        for _ in 1..n + k { for j in (1..dp.len()).rev() {
            dp[j] = (dp[j] + dp[j - 1]) % 1_000_000_007 } }
        dp[2 * k as usize]
    }