2954. Count the Number of Infection Sequences
Asked at Uber
Difficulty
Hard
Time
O(n)
Space
O(n)
Pattern
Array
Companies
1
Problem
We have n people standing in a line, numbered 0 to n-1. Some of them are already sick, and their positions are given in the sorted array sick. Everyone else is healthy.
At each step, exactly one healthy person who is next to a sick person becomes sick. This keeps going until nobody is healthy. An infection sequence is the list of healthy people in the order they got sick. People who were sick from the start are not part of the sequence.
Return how many different infection sequences are possible, modulo 10^9 + 7. Two sequences are different if the order of the newly infected people differs.
Who can get sick next
Constraints
- ●
2 <= n <= 10^5 - ●
1 <= sick.length <= n - 1 - ●
0 <= sick[i] <= n - 1 - ●
sick is sorted in increasing order
Examples
n = 5, sick = [0,4]4n = 4, sick = [1]3Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Uber | Hard | View all Uber questions → |
How to Think About It
Brute force: simulate all possible infection orders via backtracking. At each step, try every person who could be infected next. This is exponential - O(2^n) or worse. Far too slow.
Key insight: infection spreads independently between adjacent infected groups. If you sort the infected positions, the gaps between them form independent segments. The total sequences are the product of sequences for each gap multiplied by the multinomial coefficient for interleaving.
For a gap of length k between two infected boundaries: the two ends infect inward. Each step picks the left side or the right side, but the last person in the gap is forced once one side is exhausted, so an interior gap has 2^(k-1) internal orders. An edge gap (only one infected neighbor) has exactly 1.
The mathematical formula: sort infected positions. For interior gaps of lengths g1, g2, ..., the number of ways is the product of 2^(gi-1) for each gap, times the multinomial coefficient (total_healthy)! / (g1! * g2! * ...) over ALL gaps for interleaving their infection steps. Use modular arithmetic with Fermat's Little Theorem for division.
Use precomputed factorials and inverse factorials for modular combinations. Fermat's Little Theorem: a^(-1) = a^(mod-2) mod mod. Precompute factorials up to n in O(n) time.
Optimal Approach
Sort infected positions and add sentinels -1 and n. For each gap between consecutive sentinels, compute its length. Edge gaps contribute a factor of 1 (only one side to infect). Interior gaps contribute 2^(g-1) ways, since the last person in the gap is forced once one side is exhausted. Then compute the multinomial coefficient over ALL gaps: (total_healthy)! / product(g_i!). Multiply the interior-gap factors by the multinomial and return mod 10^9 + 7.
Walkthrough with n=6, infected=[2]:
Sentinels: [-1, 2, 6]. Gaps: left=2 (indices 0,1), right=3 (indices 3,4,5). Both are edge gaps, so interior factors stay 1. Multinomial over all gaps: 5! / (2! * 3!) = 10. Result: 10 - the left side (infecting 1 then 0) and the right side (infecting 3, 4, 5 in order) interleave in 10 ways.
Walkthrough with n=6, infected=[1, 4]:
Sentinels: [-1, 1, 4, 6]. Gaps: left=1 (edge), middle=2 (interior), right=1 (edge).
Interior gap of length 2: 2^(2-1) = 2 ways. Edge gaps: 1 way each.
Multinomial over all gaps: 4! / (1! * 2! * 1!) = 12.
Result: 1 * 2 * 1 * 12 = 24.
Time: O(n) with precomputed factorials. Space: O(n).
Split into independent gaps
What Trips People Up in Real Interviews
Not recognizing that gaps between infected people are independent. Once you sort the infected positions, each segment between consecutive infected people can be resolved independently.
Confusing edge gaps with interior gaps. Edge gaps (next to the boundary of the line) have only one infected neighbor, so there is exactly one internal order. Interior gaps have two sides, each step picks a side, and the last step is forced - giving 2^(g-1) orders.
Forgetting the multinomial coefficient. Even if each interior gap has 2^(g-1) internal orders, the orders across gaps interleave in time. Count the interleavings with (total)! / product(g_i!) over ALL gaps, or you undercount badly.
Not using modular arithmetic correctly. All multiplications and powers must be done mod 10^9 + 7. Division requires modular inverse via Fermat's Little Theorem.
Missing the sentinels (-1 and n). Without them, edge gaps are not handled uniformly. Add -1 and n as virtual infected positions to simplify the gap computation.
Solution Code
O(n) timedef countSequences(n, infected):
MOD = 10**9 + 7
infected.sort()
fact = [1] * (n + 1)
for i in range(1, n + 1):
fact[i] = fact[i - 1] * i % MOD
inv_fact = [1] * (n + 1)
inv_fact[n] = pow(fact[n], MOD - 2, MOD)
for i in range(n - 1, -1, -1):
inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD
sentinels = [-1] + infected + [n]
total_ways = 1
all_gaps = []
for i in range(1, len(sentinels)):
gap = sentinels[i] - sentinels[i - 1] - 1
if gap <= 0:
continue
all_gaps.append(gap)
if i > 1 and i < len(sentinels) - 1:
total_ways = total_ways * pow(2, gap - 1, MOD) % MOD
total_healthy = sum(all_gaps)
multinomial = fact[total_healthy]
for g in all_gaps:
multinomial = multinomial * inv_fact[g] % MOD
return total_ways * multinomial % MODFrequently Asked Questions
What is the Count the Number of Infection Sequences problem?
Given n people in a line (indexed 0 to n-1) and a list of infected indices, each second an uninfected person adjacent to an infected person becomes infected. Count the number of possible infection sequences (the order in which uninfected people get infected). Return the result modulo 10^9 + 7.
How do you solve Count the Number of Infection Sequences?
The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Count the Number of Infection Sequences?
Count the Number of Infection Sequences is asked at Uber. It is a hard difficulty problem.
What are common mistakes on Count the Number of Infection Sequences?
- Not recognizing that gaps between infected people are independent. Once you sort the infected positions, each segment between consecutive infected people can be resolved independently.
- Confusing edge gaps with interior gaps. Edge gaps (next to the boundary of the line) have only one infected neighbor, so there is exactly one internal order. Interior gaps have two sides, each step picks a side, and the last step is forced - giving 2^(g-1) orders.
- Forgetting the multinomial coefficient. Even if each interior gap has 2^(g-1) internal orders, the orders across gaps interleave in time. Count the interleavings with (total)! / product(g_i!) over ALL gaps, or you undercount badly.
- Not using modular arithmetic correctly. All multiplications and powers must be done mod 10^9 + 7. Division requires modular inverse via Fermat's Little Theorem.
- Missing the sentinels (-1 and n). Without them, edge gaps are not handled uniformly. Add -1 and n as virtual infected positions to simplify the gap computation.