Atlassian Algorithm Onsite Interview: Infection Sequences Problem

Infection Sequences Count

Problem Description There are $n$ houses aligned in a straight line, numbered 1 to $n$. An integer array infectedHouses represents the houses initially infected wit

Infection Sequences Count

Problem Description There are $n$ houses aligned in a straight line, numbered 1 to $n$. An integer array infectedHouses represents the houses initially infected with a virus. The virus spreads daily according to the following rules: 1. An infected house infects its immediate uninfected neighbors (left and right) on the next day. 2. The process continues until all houses are infected. An infection sequence is the specific order in which the uninfected houses become infected. Given $n$ and the initial state, determine the total number of distinct infection sequences modulo $10^9 + 7$.

Constraints * $2 \le n \le 10^5$ * $1 \le \text{length of infectedHouses} \le n-1$ * All array elements are distinct.

Approach This is a combinatorics problem involving the interleaving of independent sequences. The uninfected houses form contiguous segments (gaps) between the initially infected houses. These segments are filled independently, but their internal distinct sequences must be calculated first. 1.

Identify Segments: Sort the infectedHouses array. The uninfected houses fall into two categories: *

Boundary Segments: The gap between house 1 and the first infected house, and the gap between the last infected house and $n$. These segments have only one source of infection (one neighbor). The infection must proceed strictly from the infected neighbor outward. There is only 1 valid sequence for these segments. *

Internal Segments: The gaps between two infected houses. If the gap size is $k$, it is being infected from both ends. For a gap of size $k$, there are $2^{k-1}$ distinct ways to order the infections internally (at every step except the last, one can choose the left or right neighbor). 2.

Interleaving Sequences: Once the internal variations of the segments are determined, the segments themselves can be interleaved. If there are $m$ segments with sizes $s_1, s_2, \dots, s_m$ and the total number of uninfected houses is $S = \sum s_i$, the number of ways to interleave these processes is determined by the multinomial coefficient: $$ \frac{S!}{s_1! \cdot s_2! \cdot \dots \cdot s_m!} $$ 3.

Final Formula: $$ \text{Result} = \left( \frac{S!}{\prod (s_i!)} \right) \times \prod (\text{Internal Ways}_i) $$ Where Internal Ways is 1 for boundary segments and $2^{s_i-1}$ for internal segments.

Algorithm 1. Initialize total_count to 1 and mod to $10^9 + 7$. 2. Precompute factorials and inverse factorials for combinatorics. 3. Sort infectedHouses. 4. Calculate the total number of uninfected houses, $S = n - \text{length}(\text{infectedHouses})$. 5. Initialize numerator as $S!$. 6.

Process Left Boundary: * Size $k = \text{infectedHouses}[0] - 1$. * If $k > 0$, divide numerator by $k!$. 7.

Process Right Boundary: * Size $k = n - \text{infectedHouses}[\text{last}]$. * If $k > 0$, divide numerator by $k!$. 8.

Process Internal Gaps: * Iterate through infectedHouses from $i = 0$ to $m-2$. * Calculate gap size $k = \text{infectedHouses}[i+1] - \text{infectedHouses}[i] - 1$. * If $k > 0$: * Divide numerator by $k!$. * Multiply total_count by $2^{k-1}$. 9. Multiply total_count by numerator (which represents the multinomial coefficient logic). 10.

Return total_count % mod.

Complexity *

Time: $O(N \log N)$ due to sorting the infected array, or $O(N)$ if pre-sorted. Factorial precomputation is $O(N)$. *

Space: $O(N)$ for storing factorials.