Watch 5 video solutions for Count the Number of Infection Sequences, a hard level problem involving Array, Math, Combinatorics. This walkthrough by Soumya Bhattacharjee has 813 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.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 | 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 |