DDSA Solutions

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

MediumView on LeetCode
MathDynamic Programmingcombinatorics

Problem Overview

You must place exactly k segments on n points so they never cross interiors, though they may share an endpoint.

Intuition

You must place exactly k segments on n points so they never cross interiors, though they may share an endpoint. That counting problem collapses to a single binomial: choose 2k positions from n+k-1 after inserting k-1 glue units that encode shared joins.

Algorithm

  1. 1Recognize the answer equals C(n + k - 1, 2k) modulo 1e9+7.
  2. 2Compute the binomial multiplicatively: start at 1 and for i from 1 to r multiply by (n-r+i) then by the modular inverse of i.
  3. 3Use r = min(2k, n+k-1-2k) to keep the product short.
  4. 4Take inverses with Fermat pow since the modulus is prime.
  5. 5Return the combination as the number of valid segment sets.

Example Walkthrough

Input: n = 4, k = 2

  1. 1.Need C(4+2-1, 4) = C(5, 4).
  2. 2.That equals 5, matching the five drawings of two non-crossing segments on four points.

Output: 5

Common Pitfalls

  • •Segments must cover at least two points; length zero is illegal.
  • •Sharing an endpoint is allowed; overlapping interiors is not.
  • •Do not confuse this with C(n, 2k), which forbids shared endpoints.
  • •Always reduce modulo 1e9+7; raw factorials overflow quickly.
1621.cs
C#
// Approach: Sharing endpoints maps to C(n + k - 1, 2k): each of k segments
// needs 2 endpoints, and k-1 "glue" units encode shared joins, so pick 2k
// positions from n+k-1. Compute the binomial mod 1e9+7 multiplicatively.
// Complexity: O(k log MOD) time, O(1) extra space.
public class Solution
{
    private const int Mod = 1_000_000_007;

    public int NumberOfSets(int n, int k)
    {
        return Comb(n + k - 1, 2 * k);
    }

    // C(n, r) mod Mod via product form; uses min(r, n-r).
    private static int Comb(int n, int r)
    {
        if (r < 0 || r > n)
            return 0;
        r = Math.Min(r, n - r);
        long res = 1;
        for (int i = 1; i <= r; i++)
        {
            res = res * (n - r + i) % Mod;
            res = res * ModInverse(i) % Mod;
        }
        return (int)res;
    }

    private static long ModInverse(int a)
    {
        return ModPow(a, Mod - 2);
    }

    private static long ModPow(long baseVal, int exp)
    {
        long res = 1;
        baseVal %= Mod;
        while (exp > 0)
        {
            if ((exp & 1) == 1)
                res = res * baseVal % Mod;
            baseVal = baseVal * baseVal % Mod;
            exp >>= 1;
        }
        return res;
    }
}
Was this solution helpful?

Related Problems