#2954

Hard

LeetCode Problem Workspace

Count the Number of Infection Sequences

Calculate all valid infection sequences in a line by using array positions and combinatorial math efficiently for n people.

array math combinatorics

Problem Statement

You are given an integer n representing a line of people and an array sick indicating the indices of initially infected people. Each step, any uninfected person adjacent to an infected person can become infected. The goal is to determine all possible orders in which the remaining uninfected people become infected.

An infection sequence is defined as the order of infections excluding the initially infected people. You must compute the total number of valid sequences until everyone is infected. Consider array segments between sick positions to apply combinatorial counting efficiently.

Examples

Example 1

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

Output: 4

There is a total of 6 different sequences overall.

Example 2

Input: n = 4, sick = [1]

Output: 3

There is a total of 6 different sequences overall.

Constraints

2 <= n <= 105
1 <= sick.length <= n - 1
0 <= sick[i] <= n - 1
sick is sorted in increasing order.

Solution Approach

Segment the line by initially infected positions

Split the array into segments between the indices in sick. Each segment contains contiguous uninfected people, which can be infected in multiple orders. Modeling these segments reduces the problem to smaller combinatorial subproblems.

Use combinatorial math within segments

For each segment, count the number of ways uninfected people can be infected from both ends. This is equivalent to computing binomial coefficients for each block of size k, reflecting the order choices. Multiply segment results for the total.

Combine segment results for the final count

After computing possible sequences for all segments, multiply them together to get the total number of infection sequences. This leverages array plus math efficiently and avoids simulating all permutations explicitly.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on iterating through segments and computing combinatorial numbers, roughly O(n) with precomputed factorials. Space complexity is O(n) to store factorials and segment lengths.

What Interviewers Usually Probe

Check how you segment the array and ensure proper boundaries for combinatorial counting.
Be careful with large numbers; modular arithmetic might be necessary.
Discuss how multiplying segment results gives the final sequence count and why this works mathematically.

Common Pitfalls or Variants

Common pitfalls

Forgetting to exclude initially infected positions when counting sequences.
Miscounting orders within segments that have multiple infection possibilities.
Not handling edge segments at the ends of the line correctly.

Follow-up variants

Allowing multiple infections per step instead of one at a time changes combinatorial calculations.
Changing the line to a circular arrangement affects adjacency rules and segment counting.
Using a tree or graph structure instead of a line introduces more complex infection propagation patterns.

FAQ

How do you handle segments at the ends of the line in Count the Number of Infection Sequences?

Treat end segments as normal blocks; compute the number of infection sequences from the single adjacent infected person outward, then combine with other segments.

What pattern does this problem follow?

It follows an array plus math pattern where you divide the line into contiguous uninfected segments and use combinatorics to count sequences.

Can initially infected positions be skipped in calculations?

Yes, you exclude them from infection sequences since they do not change orderings.

Is there a faster way than simulating every infection step?

Yes, by segmenting the array and using combinatorial math, you compute total sequences without simulating all permutations.

What should I watch out for with large n values?

Use modular arithmetic and precompute factorials to prevent overflow while multiplying segment results.

terminal

Solution

Solution 1: Combinatorial Mathematics + Multiplicative Inverse + Fast Power

According to the problem description, the children who have a cold have divided the children who have not yet caught a cold into several continuous segments. We can use an array $nums$ to record the number of children who are not cold in each segment, and there are a total of $s = \sum_{i=0}^{k} nums[k]$ children who are not cold. We can find that the number of cold sequences is the number of permutations of $s$ different elements, that is, $s!$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

mod = 10**9 + 7
mx = 10**5
fac = [1] * (mx + 1)
for i in range(2, mx + 1):
    fac[i] = fac[i - 1] * i % mod


class Solution:
    def numberOfSequence(self, n: int, sick: List[int]) -> int:
        nums = [b - a - 1 for a, b in pairwise([-1] + sick + [n])]
        ans = 1
        s = sum(nums)
        ans = fac[s]
        for x in nums:
            if x:
                ans = ans * pow(fac[x], mod - 2, mod) % mod
        for x in nums[1:-1]:
            if x > 1:
                ans = ans * pow(2, x - 1, mod) % mod
        return ans

Continue Practicing

#2963 count the number of good partitions #3116 kth smallest amount with single denomination combination #3128 right triangles