LeetCode 1621: Number of Sets of K Non-Overlapping Line Segments Solution

Master LeetCode problem 1621 (Number of Sets of K Non-Overlapping Line Segments), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

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

Medium

Math Dynamic Programming Combinatorics

Problem Explanation

Explanation:

The problem can be solved using dynamic programming. We can define a 3D DP array dp where dp[i][j][l] represents the number of ways to draw l non-overlapping line segments using the first i points, with the jth point as the last point of the last segment.

For each dp[i][j][l], we can either:

Extend the last segment to include point i, increasing the count by dp[i-1][j][l].
Start a new segment at point i, increasing the count by dp[i-1][i-1][l-1].

The final result will be the sum of dp[n-1][j][k] for j from 0 to n-1.

Solution Code

class Solution {
    public int numberOfSets(int n, int k) {
        int mod = 1000000007;
        int[][][] dp = new int[n][n][k+1];
        for (int i = 0; i < n; i++) {
            dp[i][i][1] = 1;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                for (int l = 1; l <= k; l++) {
                    dp[i][j][l] = (dp[i-1][j][l] + dp[i-1][i-1][l-1]) % mod;
                }
            }
        }
        int res = 0;
        for (int j = 0; j < n; j++) {
            res = (res + dp[n-1][j][k]) % mod;
        }
        return res;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1621 (Number of Sets of K Non-Overlapping Line Segments)?

This page provides optimized solutions for LeetCode problem 1621 (Number of Sets of K Non-Overlapping Line Segments) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1621 (Number of Sets of K Non-Overlapping Line Segments)?

The time complexity for LeetCode 1621 (Number of Sets of K Non-Overlapping Line Segments) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1621 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1621 in Java, C++, or Python.

Back to LeetCode Solutions