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.
[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.
[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 - 1sick is sorted in increasing order.#2954 Count the Number of Infection Sequences is a combinatorics-heavy problem where infection spreads from initially infected positions to neighboring healthy people. The key observation is that healthy segments between infected people behave independently but interact through the ordering of infections.
Start by sorting the infected indices and identifying the gaps of healthy people between them. Edge gaps (before the first infected and after the last) can only be infected from one direction, while middle gaps can be infected from both ends simultaneously. For each middle gap of length g, multiple internal infection orders exist due to two-directional spread.
The total number of valid sequences can be computed using combinatorics. First distribute infection events across all gaps using factorial-based counting (multinomial idea). Then multiply by additional arrangements contributed by middle gaps. Precompute factorials and modular inverses to efficiently evaluate combinations under modulo arithmetic.
This leads to an efficient solution with linear preprocessing and fast combinatorial calculations.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Gap analysis with combinatorics and precomputed factorials | O(n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Consider infected children as <code>0</code> and non-infected as <code>1</code>, then divide the array into segments with the same value.
For each segment of non-infected children whose indices are <code>[i, j]</code> and indices <code>(i - 1)</code> and <code>(j + 1)</code>, if they exist, are already infected. Then if <code>i == 0</code> or <code>j == n - 1</code>, each second there is only one kid that can be infected (which is at the other endpoint).
If <code>i > 0</code> and <code>j < n - 1</code>, we have two choices per second since the children at the two endpoints can both be the infect candidates. So there are <code>2<sup>j - i</sup></code> orders to infect all children in the segment.
Each second we can select a segment and select one endpoint from it.
The answer is: <code>S! / (len[1]! * len[2]! * ... * len[m]! * len<sub>start</sub>! * len<sub>end</sub>!) * 2<sup>k</sup></code> where <code>len[1], len[2], ..., len[m]</code> are the lengths of each segment of non-infected children that have an infected child at both endpoints, <code>len<sub>start</sub></code> and <code>len<sub>end</sub></code> denote the number of non-infected children with infected child at one endpoint, <code>S</code> is the total length of all segments of non-infected children, and <code>k = (len[1] - 1) + (len[2] - 1) + ... + (len[m] - 1)</code>.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems involving combinatorics, gap analysis, and counting sequences appear frequently in advanced coding interviews. While this exact problem may not always appear, the techniques used are highly relevant for top tech company interviews.
The optimal approach analyzes gaps of healthy people between infected indices and uses combinatorics to count valid infection orders. Factorials and modular inverses are used to compute multinomial distributions efficiently under modulo constraints.
Key concepts include combinatorics, factorial precomputation, modular arithmetic, and array gap analysis. Understanding multinomial counting and powers for two-sided spread is essential.
Middle gaps have infected people on both sides, meaning the infection can spread inward from two directions. This creates additional ordering possibilities compared to edge gaps, which only receive infection from one side.