Count the Number of Infection Sequences solution and explanation
5 more videos on this problem
Count the Number of Infection Sequences (Leetcode Weekly 374)Soumya Bhattacharjee · 9:59 · 902 views
Count Number of Infection Sequences - LeetCode 2954 - PythonAlpha-Code · 32:56 · 878 views
2954. Count the Number of Infection Sequences (Leetcode Hard)Programming Live with Larry · 46:56 · 781 views
【每日一题】LeetCode 2954. Count the Number of Infection SequencesHuifeng Guan · 34:10 · 360 views
[LC-WC-374] Count the Number of Infection SequencesBeing Zero · 27:58 · 220 views
Leetcode Weekly 374 || CountCompleteSubstrings || Count the number infection SequencesCodeClub · 0:11 · 143 views
The 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.
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.
MOD = 10**9 + 7
def count_infection_sequences(n, sick):
from math import factorial
fact = [1] * (n + 1)
for i in range(2, n + 1):
fact[i] = fact[i - 1] * i % MOD
sick = [-1] + sick + [n]
total_sequences = 1
for i in range(1, len(sick)):
gap = sick[i] - sick[i - 1] - 1
if gap > 0:
total_sequences = total_sequences * fact[gap] % MOD
return total_sequences
# Example usage
n = 5
sick = [0, 4]
print(count_infection_sequences(n, sick)) # Output: 4#include <iostream>
#include <vector>
#include <cmath>
const int MOD = 1e9 + 7;
long long factorial(int n) {
long long result = 1;
for (int i = 2; i <= n; ++i)
result = (result * i) % MOD;
return result;
}
int countInfectionSequences(int n, const std::vector<int>& sick) {
std::vector<int> extendedSick = {-1};
extendedSick.insert(extendedSick.end(), sick.begin(), sick.end());
extendedSick.push_back(n);
int totalSequences = 1;
for (size_t i = 1; i < extendedSick.size(); ++i) {
int gap = extendedSick[i] - extendedSick[i - 1] - 1;
if (gap > 0) {
totalSequences = (totalSequences * factorial(gap)) % MOD;
}
}
return totalSequences;
}
int main() {
int n = 5;
std::vector<int> sick = {0, 4};
std::cout << countInfectionSequences(n, sick) << std::endl; // Output: 4
return 0;
}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.
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.
import java.util.Arrays;
public class InfectionSequences {
private static final int MOD = 1_000_000_007;
private static int countInfectionSequences(int n, int[] sick) {
sick = Arrays.copyOf(sick, sick.length + 2);
int len = sick.length;
sick[len - 1] = n;
int[][] comb = new int[n + 1][n + 1];
for (int i = 0; i <= n; i++) {
comb[i][0] = comb[i][i] = 1;
for (int j = 1; j < i; j++) {
comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % MOD;
}
}
sick[0] = -1;
int totalSequences = 1;
for (int i = 1; i < len; ++i) {
int gap = sick[i] - sick[i - 1] - 1;
if (gap > 0) {
totalSequences = (totalSequences * comb[gap][gap]) % MOD;
}
}
return totalSequences;
}
public static void main(String[] args) {
int n = 5;
int[] sick = {0, 4};
System.out.println(countInfectionSequences(n, sick)); // Output: 4
}
}const MOD = 1e9 + 7;
function factorial(n) {
let result = 1;
for (let i = 2; i <= n; i++) {
result = (result * i) % MOD;
}
return result;
}
function countInfectionSequences(n, sick) {
sick = [-1, ...sick, n];
let totalSequences = 1;
for (let i = 1; i < sick.length; i++) {
let gap = sick[i] - sick[i - 1] - 1;
if (gap > 0) {
totalSequences = totalSequences * factorial(gap) % MOD;
}
}
return totalSequences;
}
console.log(countInfectionSequences(5, [0, 4])); // Output: 4This 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.
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)$.
const MX = 1e5;
const MOD: bigint = BigInt(1e9 + 7);
const fac: bigint[] = Array(MX + 1);
const init = (() => {
fac[0] = 1n;
for (let i = 1; i <= MX; ++i) {
fac[i] = (fac[i - 1] * BigInt(i)) % MOD;
}
return 0;
})();
function qpow(a: bigint, n: number): bigint {
let ans = 1n;
for (; n > 0; n >>= 1) {
if (n & 1) {
ans = (ans * a) % MOD;
}
a = (a * a) % MOD;
}
return ans;
}
function numberOfSequence(n: number, sick: number[]): number {
const m = sick.length;
const nums: number[] = Array(m + 1);
nums[0] = sick[0];
nums[m] = n - sick[m - 1] - 1;
for (let i = 1; i < m; i++) {
nums[i] = sick[i] - sick[i - 1] - 1;
}
const s = nums.reduce((acc, x) => acc + x, 0);
let ans = fac[s];
for (let x of nums) {
if (x > 0) {
ans = (ans * qpow(fac[x], Number(MOD) - 2)) % MOD;
}
}
for (let i = 1; i < nums.length - 1; ++i) {
if (nums[i] > 1) {
ans = (ans * qpow(2n, nums[i] - 1)) % MOD;
}
}
return Number(ans);
}const MX = 1e5
const MOD = 1e9 + 7
var fac [MX + 1]int
func init() {
fac[0] = 1
for i := 1; i <= MX; i++ {
fac[i] = fac[i-1] * i % MOD
}
}
func qpow(a, n int) int {
ans := 1
for n > 0 {
if n&1 == 1 {
ans = (ans * a) % MOD
}
a = (a * a) % MOD
n >>= 1
}
return ans
}
func numberOfSequence(n int, sick []int) int {
m := len(sick)
nums := make([]int, m+1)
nums[0] = sick[0]
nums[m] = n - sick[m-1] - 1
for i := 1; i < m; i++ {
nums[i] = sick[i] - sick[i-1] - 1
}
s := 0
for _, x := range nums {
s += x
}
ans := fac[s]
for _, x := range nums {
if x > 0 {
ans = ans * qpow(fac[x], MOD-2) % MOD
}
}
for i := 1; i < len(nums)-1; i++ {
if nums[i] > 1 {
ans = ans * qpow(2, nums[i]-1) % MOD
}
}
return ans
}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 | – |
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 |
Frequently asked questions
Is Count the Number of Infection Sequences easy or hard?
Count the Number of Infection Sequences is classified as a Hard problem. It requires recognizing how infection spreads across segments and converting that process into a combinatorial counting formula using binomial coefficients and powers of two.
Count the Number of Infection Sequences Python/Java solution
Python and C++ implementations typically use precomputed factorial arrays and modular inverse functions to evaluate combinations. Java and JavaScript solutions follow the same combinatorial formula but implement modular exponentiation and binomial coefficient helpers explicitly.
How to solve Count the Number of Infection Sequences in O(n)?
Sort the infected indices and determine the lengths of healthy gaps between them. Use combinatorics to count ways to distribute infection events across segments, multiplying binomial coefficients and powers of two for internal gaps. Precompute factorials and modular inverses so each combination calculation runs in constant time.
What is the best approach for Count the Number of Infection Sequences?
The combinatorial binomial coefficient approach is the most efficient and commonly expected solution. It models infection spread as arrangements of events across independent segments and computes the result using factorials and modular inverses. This achieves O(n) time and O(n) space complexity after preprocessing.
Is Count the Number of Infection Sequences asked at Google/Amazon/Meta?
Problems involving combinatorics, segment counting, and modular arithmetic frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that require counting sequences or arrangements under constraints are especially common in senior-level coding rounds.
What data structure is used in Count the Number of Infection Sequences?
The solution mainly uses arrays to store factorial values and segment lengths. The core logic relies more on mathematical combinatorics than complex data structures, combined with modular arithmetic for large numbers.
What is the time complexity of Count the Number of Infection Sequences?
The optimal solution runs in O(n) time with O(n) space. The algorithm processes the infected indices once to compute segment lengths and uses precomputed factorials to evaluate binomial coefficients efficiently.