1621 LeetCode problem solution

LeetCode problem link: 1621. Number of Sets of K Non-Overlapping Line Segments

LeetCode 1621 problem description

Medium level 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 to 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 to draw k non-overlapping line segments. Since the answer can be very large, return it modulo 10⁹ + 7.

Example 1:

Input: n = 4, k = 2
Output: 5

Explanation: The two line segments are shown in red and blue. The image above shows the 5 different ways {(0,2),(2,3)}, {(0,1),(1,3)}, {(0,1),(2,3)}, {(1,2),(2,3)}, {(0,1),(1,2)}.

Example 2:

Input: n = 3, k = 1
Output: 3

Explanation: The three possible segments are (0, 1), (0, 2), and (1, 2).

Example 3:

Input: n = 30, k = 7
Output: 796297179
Explanation: The total number of possible ways to draw 7 line segments is 3796297200. Taking this number modulo 109 + 7 gives us 796297179.

Constraints:

2 <= n <= 1000
1 <= k <= n - 1

LeetCode 1621 problem: solution explanation

This problem can be solved using Combinatorics.

We need to choose exactly k non-overlapping line segments from n points.

A segment is determined by two endpoints, so k segments have 2 * k endpoints. The difficulty is that neighboring segments are allowed to share an endpoint.

For example:

[0, 2] and [2, 3]

are valid because the two segments only meet at point 2.

The main idea is to transform the endpoints so that shared endpoints become different positions. After this transformation, the problem becomes choosing 2 * k different positions from n + k - 1 positions.

Therefore, the answer is:

C(n + k - 1, 2 * k)

Step 1: Describe the segment endpoints

Suppose the k segments are:

[s1, e1], [s2, e2], ..., [sk, ek]

For every segment, the start must be smaller than the end:

s1 < e1
s2 < e2
...
sk < ek

The segments cannot overlap, but they can share endpoints.

Therefore:

0 <= s1 < e1 <= s2 < e2 <= ... <= sk < ek <= n - 1

For example:

[0, 2], [2, 3]

gives:

0 < 2 <= 2 < 3

The important part is:

e1 <= s2

and not:

e1 < s2

because e1 and s2 may represent the same point.

Step 2: Transform shared endpoints

If all endpoints were different, we could simply choose 2 * k different points.

But shared endpoints make this impossible directly.

To remove this problem, we shift the endpoints of each next segment by one additional position.

For the first segment:

z1 = s1
z2 = e1

For the second segment:

z3 = s2 + 1
z4 = e2 + 1

For the third segment:

z5 = s3 + 2
z6 = e3 + 2

In general, for segment i:

z(2i - 1) = si + i - 1
z(2i)     = ei + i - 1

Now all transformed values are strictly increasing:

z1 < z2 < z3 < z4 < ... < z(2k)

Consider two segments that share an endpoint:

e1 = s2 = 2

Before the transformation:

e1 = 2
s2 = 2

After the transformation:

z2 = e1 = 2
z3 = s2 + 1 = 3

The shared point becomes two different positions.

This allows us to treat all 2 * k transformed endpoints as distinct.

Step 3: Count the available transformed positions

Originally, the points are:

0, 1, 2, ..., n - 1

The last segment is shifted by:

k - 1

Therefore, the largest transformed endpoint can be:

(n - 1) + (k - 1)

which is:

n + k - 2

So the transformed positions are:

0, 1, 2, ..., n + k - 2

There are:

n + k - 1

possible positions.

We need to choose exactly:

2 * k

of them.

Therefore:

answer = C(n + k - 1, 2 * k)

Here, C(N, R) represents a combination - the number of ways to choose R elements from N elements without considering their order.

Step 4: Example

For:

n = 4
k = 2

we have:

N = n + k - 1
N = 4 + 2 - 1
N = 5

and:

R = 2 * k
R = 4

Therefore:

C(5, 4) = 5

This means there are 5 ways to choose 4 transformed endpoints from 5 positions.

These correspond exactly to the 5 valid sets of two non-overlappingsegments.

Step 5: Calculate the combination efficiently

We only need to calculate one combination:

C(N, R)

where:

N = n + k - 1
R = 2 * k

Combinations have the property:

C(N, R) = C(N, N - R)

Therefore, we use:

R = min(R, N - R);

For this problem:

N - R = n + k - 1 - 2k = n - k - 1

so we actually need only:

R = min(2 * k, n - k - 1)

For example:

C(5, 4) = C(5, 1)

Instead of performing 4 iterations, we only need 1.

This does not change the result, but reduces the number of calculations.

We calculate the combination multiplicatively:

C(N, R) = N * (N - 1) * ... * (N - R + 1)
          ---------------------------------
                  1 * 2 * ... * R

Because division cannot be performed directly under modulo 10⁹ + 7, we use modular inverses.

We precompute modular inverses only up to R:

inv[i] = MOD - (MOD / i) * inv[MOD % i] % MOD;

Then we calculate the combination:

result = result * (N - R + i) % MOD;
result = result * inv[i] % MOD;

LeetCode 1621 problem: complexity

After:

R = min(R, N - R);

we have:

R = min(2 * k, n - k - 1)

We precompute modular inverses from 1 to R and calculate the combination in another R iterations.

Time complexity: O(R)
Space complexity: O(R)

where:

R = min(2 * k, n - k - 1)

In the worst case, both are O(n).

Pattern: Combinatorics
Technique: Endpoint Transformation, Binomial Coefficient, Modular Arithmetic

LeetCode 1621 C++ solution

class Solution {
public:
  static constexpr long long MOD = 1'000'000'007;

  int numberOfSets(int n, int k)
  {
    int N = n + k - 1;
    int R = 2 * k;

    R = min(R, N - R);

    vector<long long> inv(R + 1);

    if(R >= 1) inv[1] = 1;

    for(int i = 2; i <= R; i++)
      inv[i] = MOD - (MOD / i) * inv[MOD % i] % MOD;

    long long result = 1;

    for(int i = 1; i <= R; i++)
    {
      result = result * (N - R + i) % MOD;
      result = result * inv[i] % MOD;
    }

    return result;
  }
};

LeetCode 1621 Java solution

class Solution {
  static final long MOD = 1_000_000_007L;

  public int numberOfSets(int n, int k) {
    int N = n + k - 1;
    int R = 2 * k;

    R = Math.min(R, N - R);

    long[] inv = new long[R + 1];

    if(R >= 1) inv[1] = 1;

    for(int i = 2; i <= R; i++)
      inv[i] = MOD - (MOD / i) * inv[(int)(MOD % i)] % MOD;

    long result = 1;

    for(int i = 1; i <= R; i++) {
      result = result * (N - R + i) % MOD;
      result = result * inv[i] % MOD;
    }

    return (int)result;
  }
}

LeetCode 1621 JavaScript solution

var numberOfSets = function(n, k) {
  const MOD = 1000000007n;

  const N = n + k - 1;
  let R = 2 * k;

  R = Math.min(R, N - R);

  const inv = new Array(R + 1).fill(0n);

  if(R >= 1) inv[1] = 1n;

  for(let i = 2; i <= R; i++) {
    const bi = BigInt(i);
    inv[i] = MOD - (MOD / bi) * inv[Number(MOD % bi)] % MOD;
  }

  let result = 1n;

  for(let i = 1; i <= R; i++) {
    result = result * BigInt(N - R + i) % MOD;
    result = result * inv[i] % MOD;
  }

  return Number(result);
};

LeetCode 1621 TypeScript solution

function numberOfSets(n: number, k: number): number {
  const MOD = 1000000007n;

  const N: number = n + k - 1;
  let R: number = 2 * k;

  R = Math.min(R, N - R);

  const inv: bigint[] = new Array(R + 1).fill(0n);

  if(R >= 1) inv[1] = 1n;

  for(let i = 2; i <= R; i++) {
    const bi = BigInt(i);
    inv[i] = MOD - (MOD / bi) * inv[Number(MOD % bi)] % MOD;
  }

  let result: bigint = 1n;

  for(let i = 1; i <= R; i++) {
    result = result * BigInt(N - R + i) % MOD;
    result = result * inv[i] % MOD;
  }

  return Number(result);
}

LeetCode 1621 Python solution

class Solution:
  MOD = 10**9 + 7

  def numberOfSets(self, n: int, k: int) -> int:
    N = n + k - 1
    R = 2 * k

    R = min(R, N - R)

    inv = [0] * (R + 1)

    if R >= 1: inv[1] = 1

    for i in range(2, R + 1):
      inv[i] = (self.MOD - (self.MOD // i) * inv[self.MOD % i] % self.MOD)

    result = 1

    for i in range(1, R + 1):
      result = result * (N - R + i) % self.MOD
      result = result * inv[i] % self.MOD

    return result