Count the Number of Infection Sequences - Solution & Explanation
Problem Statement
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.
Example 1:
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:
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 <= 1051 <= sick.length <= n - 10 <= sick[i] <= n - 1sickis sorted in increasing order.
Approach Overview
Problem Overview: You are given n people in a line and a list of initially infected indices. Each day infection spreads to adjacent healthy people. The task is to count how many valid sequences of infection events can occur until everyone becomes infected.
The key observation is that infection spreads inside the gaps between initially infected people. Each gap behaves like a small independent segment where the order of infections can vary, and the total number of global sequences comes from combining these possibilities using combinatorics.
Approach 1: Dynamic Programming Approach (O(n) time, O(n) space)
First sort the infected indices and compute the sizes of the healthy segments between them. For each segment, calculate how many ways infection can propagate from the boundaries toward the middle. A dynamic programming table helps count valid interleavings of infections across segments while maintaining the order constraints inside each segment. The DP effectively combines segment contributions using factorial-style transitions. This approach is easier to reason about step by step and works well if you want a constructive counting method. It relies on ideas from dynamic programming and sequential state transitions.
Approach 2: Combinatorial Binomial Coefficient Approach (O(n) time, O(n) space)
Instead of simulating sequences, compute them directly using combinatorics. After sorting the infected indices, calculate the lengths of the healthy gaps. The total number of ways to distribute infection events across segments equals a multinomial arrangement of all healthy positions. For middle segments (bounded by two infected nodes), infections can expand from both ends, which introduces additional 2^(len-1) possibilities for internal ordering. Use factorials and modular inverses to compute binomial coefficients efficiently. This approach leverages concepts from math and combinatorics to produce the optimal counting formula.
Recommended for interviews: The combinatorial solution is what most interviewers expect. It shows you can transform a process simulation into a counting problem using binomial coefficients and segment analysis. A DP explanation still helps demonstrate understanding of how infection orders arise before compressing the logic into the mathematical formula.
Approach 1: Dynamic Programming Approach
This approach leverages dynamic programming to count the possible infection sequences. We calculate factorial values up to n to determine the permutations count. Using the infected positions, determine contiguous uninfected segments and compute the possibilities for each segment.
We compute factorial values to facilitate permutation calculations. The list sick is extended with extra boundaries to simplify calculations. For each gap between infected, we use the permutation count for a group of uninfected as calculated by the factorial.
Complexity
Time Complexity: O(n) due to precomputation of factorials in the worst case.
Space Complexity: O(n) for storing factorial values.
Approach 2: Combinatorial Binomial Coefficient Approach
By viewing the sequence completion per gap as selecting positions of infection order, this approach uses combinatorial mathematics directly. Each gap is treated as a sequence whose arrangement counts are determined via binomial coefficients from combinatorics.
This Java code relies on the precomputation of binomial coefficients, providing the tools needed for understanding permutations of infection sequence combinations over gaps. Every independent infection per gap can be modeled this way.
Code
Java
JavaScript
Complexity
Time Complexity: O(n^2) due to the computation and storage of binomial coefficients.
Space Complexity: O(n^2) for the combinatorial table.
Approach 3: 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!.
Assuming that there is only one transmission scheme for each segment of children who are not cold, there are \frac{s!}{\prod_{i=0}^{k} nums[k]!} cold sequences in total.
Next, we consider the transmission scheme of each segment of children who are not cold. Suppose there are x children in a segment who are not cold, then they have 2^{x-1} transmission schemes, because each time you can choose one end from the left and right ends of a segment to transmit, that is: two choices, there are a total of x-1 transmissions. However, if it is the first segment or the last segment, there is only one choice.
In summary, the total number of cold sequences is:
$
\frac{s!}{\prod_{i=0}^{k} nums[k]!} \prod_{i=1}^{k-1} 2^{nums[i]-1}
Finally, we need to consider that the answer may be very large and need to be modulo 10^9 + 7. Therefore, we need to preprocess the factorial and multiplicative inverse.
The time complexity is O(m), where m is the length of the array sick. Ignoring the space consumption of the preprocessing array, the space complexity is O(m)$.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n) due to precomputation of factorials in the worst case. |
| Combinatorial Binomial Coefficient Approach | Time Complexity: O(n^2) due to the computation and storage of binomial coefficients. |
| Combinatorial Mathematics + Multiplicative Inverse + Fast Power | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(n) | O(n) | When you want a step-by-step counting model that mirrors how infections expand across segments |
| Combinatorial Binomial Coefficient | O(n) | O(n) | Best for large constraints and interviews; computes total sequences directly using factorials and modular inverses |
Video Solution
Count the Number of Infection Sequences (Leetcode Weekly 374) • Soumya Bhattacharjee • 902 views views
Watch 5 more video solutions →Frequently Asked Questions
Is Count the Number of Infection Sequences easy or hard?
Count the Number of Infection Sequences Python/Java solution
How to solve Count the Number of Infection Sequences in O(n)?
What is the best approach for Count the Number of Infection Sequences?
Is Count the Number of Infection Sequences asked at Google/Amazon/Meta?
What data structure is used in Count the Number of Infection Sequences?
What is the time complexity of Count the Number of Infection Sequences?
Ready to solve this problem?
Practice Count the Number of Infection Sequences with our built-in code editor and test cases.
Practice on FleetCode