Count the Number of Infection Sequences
Asked at Uber
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.
Asked At
| 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.
Visual walkthrough for 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 (person 2 then 3, or 3 then 2). Edge gaps: 1 way each.
Multinomial over all gaps: 4! / (1! * 2! * 1!) = 12.
Result: 1 * 2 * 1 * 12 = 24.
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).
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.