Problem

You are given an integer n and an array sick sorted in increasing order, representing positions of infected people in a line of n people.

At each step, one uninfected person adjacent to an infected person gets infected. This process continues until everyone is infected.

An infection sequence is the order in which uninfected people become infected, excluding those initially infected.

Return the number of different infection sequences possible, modulo 109+7.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


Input: n = 5, sick = [0,4]

Output: 4

Explanation:

There is a total of 6 different sequences overall.

  * Valid infection sequences are `[1,2,3]`, `[1,3,2]`, `[3,2,1]` and `[3,1,2]`.
  * `[2,3,1]` and `[2,1,3]` are not valid infection sequences because the person at index 2 cannot be infected at the first step.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


Input: n = 4, sick = [1]

Output: 3

Explanation:

There is a total of 6 different sequences overall.

  * Valid infection sequences are `[0,2,3]`, `[2,0,3]` and `[2,3,0]`.
  * `[3,2,0]`, `[3,0,2]`, and `[0,3,2]` are not valid infection sequences because the infection starts at the person at index 1, then the order of infection is 2, then 3, and hence 3 cannot be infected earlier than 2.

Constraints

  • 2 <= n <= 10^5
  • 1 <= sick.length <= n - 1
  • 0 <= sick[i] <= n - 1
  • sick is sorted in increasing order.

Solution

Method 1 – Combinatorics with Gaps and Multinomial Coefficient

Intuition

Each initially sick person infects adjacent people, and the infection spreads outwards. The only choices are the order in which the gaps between sick people are filled. For each gap, the infection can spread from either side, but the first and last gaps (at the ends) can only be filled from one side. The number of infection sequences is the multinomial coefficient of the total number of uninfected people, divided by the factorials of the sizes of the gaps, and multiplied by 2^k, where k is the number of internal gaps (since each internal gap can be filled from either side).

Approach

  1. Let gaps be the list of sizes of uninfected segments between sick people.
  2. For each internal gap (not at the ends), multiply the answer by 2^gap_size (since each person in the gap can be infected from either side, but the first and last must be filled from one side only).
  3. The total number of infection sequences is the multinomial coefficient: (total_uninfected)! / (gap1! * gap2! * … * gapk!) * (2^number_of_internal_gaps).
  4. Use modular arithmetic for large numbers.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution:
    def countInfectionSequences(self, n: int, sick: list[int]) -> int:
        MOD = 10**9 + 7
        from math import comb
        def modinv(a):
            return pow(a, MOD-2, MOD)
        sick = sorted(sick)
        gaps = []
        if sick[0] > 0:
            gaps.append(sick[0])
        for i in range(1, len(sick)):
            if sick[i] - sick[i-1] > 1:
                gaps.append(sick[i] - sick[i-1] - 1)
        if sick[-1] < n-1:
            gaps.append(n-1 - sick[-1])
        total = sum(gaps)
        fact = [1] * (total+2)
        for i in range(1, total+2):
            fact[i] = fact[i-1] * i % MOD
        ans = fact[total]
        for g in gaps:
            ans = ans * modinv(fact[g]) % MOD
        # For internal gaps, multiply by 2^(gap_size-1) for each
        for i in range(1, len(sick)):
            gap = sick[i] - sick[i-1] - 1
            if gap > 0:
                ans = ans * pow(2, gap-1, MOD) % MOD
        return ans

Complexity

  • ⏰ Time complexity: O(n) for factorial precomputation and gap processing.
  • 🧺 Space complexity: O(n) for factorials and gaps.