LeetCode Solutions Blog

Count the Number of Infection Sequences

Difficulty: Hard

Problem Description

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 10^9+7.

Key Insights

The infection spreads from infected individuals to adjacent uninfected individuals.
The sequence of infection is constrained by the positions of the initially infected individuals.
The number of valid infection sequences can be determined using combinatorial mathematics, specifically by considering gaps between infected individuals and the positions of uninfected individuals.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we will follow these steps:

Identify the gaps between the infected individuals.
For each gap, calculate the number of uninfected individuals that can be infected.
Use combinatorial counting (factorial and combinations) to determine the number of valid sequences.
Multiply the counts from each gap to get the total number of infection sequences.
Return the result modulo 10^9 + 7.

We will use arrays to store factorials and their inverses to efficiently calculate combinations.

Code Solutions

MOD = 10**9 + 7

def count_infection_sequences(n, sick):
    sick_count = len(sick)
    total_uninfected = n - sick_count
    gaps = []

    # Calculate gaps between sick individuals and the ends
    if sick[0] > 0:
        gaps.append(sick[0])  # gap before the first sick
    for i in range(1, sick_count):
        gaps.append(sick[i] - sick[i - 1] - 1)  # gaps between sick individuals
    if sick[-1] < n - 1:
        gaps.append(n - 1 - sick[-1])  # gap after the last sick

    # Precompute factorials and inverse factorials
    fact = [1] * (total_uninfected + 1)
    for i in range(2, total_uninfected + 1):
        fact[i] = fact[i - 1] * i % MOD

    def mod_inv(x):
        return pow(x, MOD - 2, MOD)

    inv_fact = [1] * (total_uninfected + 1)
    inv_fact[total_uninfected] = mod_inv(fact[total_uninfected])
    for i in range(total_uninfected - 1, 0, -1):
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD

    # Count the number of valid sequences
    result = 1
    uninfected_left = total_uninfected
    for gap in gaps:
        # Ways to choose 'gap' from 'uninfected_left'
        result = result * fact[uninfected_left] * inv_fact[gap] % MOD * inv_fact[uninfected_left - gap] % MOD
        uninfected_left -= gap

    return result

# Example usage
print(count_infection_sequences(5, [0, 4]))  # Output: 4