Count the Number of Infection Sequences
HardPrompt
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.
- Valid infection sequences are
[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.
- Valid infection sequences are
[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 - 1sickis sorted in increasing order.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the infection process step-by-step. It uses a recursive (backtracking) method to explore every possible valid sequence of infections. Starting with the initially sick people, at each step, we identify all uninfected individuals who can be infected next. We then branch out the recursion for each of these possibilities. The process continues until all individuals are infected. The total count of reaching this final state gives the answer.
Algorithm
- Define a recursive function, say
countSequences(infectedSet), which takes the current set of infected people as input. - The initial call would be with a set containing all people from the
sickarray. - Base Case: If the size of
infectedSetequalsn, it means everyone is infected. We have found one valid sequence, so return 1. - Recursive Step:
- Identify all possible next people to be infected. These are the
candidates: uninfected people who are adjacent to at least one person ininfectedSet. - Initialize a counter for the number of sequences,
count = 0. - For each
candidate:- Add the
candidateto a temporaryinfectedSet. - Recursively call
countSequenceswith the new set and add the result tocount. - Backtrack by removing the
candidate(this step is implicitly handled by passing new sets or creating copies).
- Add the
- Identify all possible next people to be infected. These are the
- Return the total
count, ensuring all additions are performed modulo10^9 + 7.
Walkthrough
The brute-force approach relies on a depth-first search of the state space, where a state is defined by the set of people who are currently infected.
We can implement this with a recursive function. This function would explore all valid next moves (infecting an adjacent person) from the current state. When a state is reached where all n people are infected, we have successfully generated one full infection sequence and can count it.
For example, if n=5 and sick=[0,4], the initial infected set is {0, 4}. The candidates for the first infection are person 1 (adjacent to 0) and person 3 (adjacent to 4). The algorithm would recursively explore both paths:
- Infect person 1. The new infected set is
{0, 1, 4}. Recurse from this state. - Infect person 3. The new infected set is
{0, 3, 4}. Recurse from this state.
This continues until the infected set contains all people from 0 to 4. Due to the massive number of possible paths, this method is too slow for the given constraints but serves as a conceptual starting point.
// This is a conceptual example and will be too slow for the given constraints.import java.util.HashSet;import java.util.Set; class Solution { private static final int MOD = 1_000_000_007; private int n; public int numberOfSequence(int n, int[] sick) { this.n = n; Set<Integer> infected = new HashSet<>(); for (int s : sick) { infected.add(s); } return countSequences(infected); } private int countSequences(Set<Integer> infected) { if (infected.size() == n) { return 1; } Set<Integer> candidates = new HashSet<>(); for (int i = 0; i < n; i++) { if (!infected.contains(i)) { if ((i > 0 && infected.contains(i - 1)) || (i < n - 1 && infected.contains(i + 1))) { candidates.add(i); } } } if (candidates.isEmpty()) { return 0; // Should not happen in a valid process } long count = 0; for (int candidate : candidates) { Set<Integer> nextInfected = new HashSet<>(infected); nextInfected.add(candidate); count = (count + countSequences(nextInfected)) % MOD; } return (int) count; }}Complexity
Time
O(k!) where k is the number of uninfected people. The branching factor can be large, leading to an explosion in the number of recursive calls. This is an exponential time complexity.
Space
O(n^2) or O(n * k) where k is the number of uninfected people. The recursion depth can be up to `n - sick.length`, and at each level, we store a set of infected people of size up to `n`.
Trade-offs
Pros
Conceptually simple and directly follows the problem's description of the infection process.
Easy to implement for small test cases.
Cons
Extremely inefficient due to its exponential time complexity.
Will result in a 'Time Limit Exceeded' (TLE) error for the constraints given in the problem.
May lead to stack overflow for large
ndue to deep recursion.Requires memoization to be even slightly feasible, but the state space (2^n) is too large to memoize effectively.
A much more efficient approach is to reframe the problem from a simulation into a combinatorial counting problem. The key insight is that the initially sick people partition the line into several independent segments of uninfected people. The total number of infection sequences can be calculated by combining two main factors:
- The number of ways to determine the infection order within each segment.
- The number of ways to interleave the infection steps from different segments.
This method avoids exploring individual sequences and instead calculates the total count directly using mathematical formulas, leading to a highly efficient solution.
Algorithm
- Step 1: Precompute Factorials. Calculate factorials up to
nmodulo10^9 + 7to be used for combinations. - Step 2: Identify Uninfected Segments. The initially sick people divide the line into segments of healthy people. Calculate the length of each of these segments.
- Segment before the first sick person:
sick[0]. - Segments between
sick[i-1]andsick[i]:sick[i] - sick[i-1] - 1. - Segment after the last sick person:
n - 1 - sick[sick.length - 1].
- Segment before the first sick person:
- Step 3: Calculate Internal Orderings. For each segment of length
kthat is between two sick groups, there are2^(k-1)ways to infect it, as the infection can spread from either side. For segments at the ends of the line, there's only 1 way. Multiply these values together to get the total number of internal ways. - Step 4: Calculate Interleaving Combinations. The infections across different segments are interleaved. If the segment lengths are
k_1, k_2, ...and the total number of uninfected people isT, the number of ways to interleave them is given by the multinomial coefficientT! / (k_1! * k_2! * ...). - Step 5: Combine Results. The final answer is the product of the total internal orderings and the interleaving combinations, all calculated modulo
10^9 + 7. Use modular inverse for division.
Walkthrough
This approach breaks the problem down into smaller, independent parts that can be solved with combinatorial formulas.
1. Segments and Internal Orderings
- The
sickarray creates segments of uninfected people. For example,n=10, sick=[2, 7]creates segments[0,1],[3,4,5,6], and[8,9]. - End Segments: A segment at an end (e.g.,
[0,1]or[8,9]) is adjacent to only one infected group. The infection must spread sequentially from that side. Thus, there is only 1 way to infect an end segment. - Middle Segments: A segment of length
kbetween two infected groups (e.g.,[3,4,5,6]) can be infected from either the left or the right. For the firstk-1infections within this segment, there are always two choices. This results in2^(k-1)possible internal orderings.
2. Interleaving Segments
- Let the lengths of the uninfected segments be
k_1, k_2, ..., k_m. The total number of people to infect isT = k_1 + k_2 + ... + k_m. - We have
Ttotal infection steps to perform. The problem is equivalent to arrangingTitems where there arek_1of type 1,k_2of type 2, etc. The number of ways to do this is given by the multinomial coefficient:T! / (k_1! * k_2! * ... * k_m!).
3. Final Calculation
The total number of sequences is the product of these two parts, calculated modulo MOD = 10^9 + 7.
Result = (Total Internal Ways) * (Interleaving Combinations) % MOD
To implement this, we need functions for modular exponentiation (for 2^(k-1) and modular inverse) and precomputed factorials.
class Solution { private static final int MOD = 1_000_000_007; private long[] fact; public int numberOfSequence(int n, int[] sick) { fact = new long[n + 1]; precomputeFactorials(n); long totalUninfected = n - sick.length; long internalWays = 1; long combinationsDenominator = 1; // First segment (before sick[0]) int firstSegmentLength = sick[0]; if (firstSegmentLength > 0) { combinationsDenominator = fact[firstSegmentLength]; } // Middle segments (between sick[i-1] and sick[i]) for (int i = 1; i < sick.length; i++) { int segmentLength = sick[i] - sick[i - 1] - 1; if (segmentLength > 0) { internalWays = (internalWays * power(2, segmentLength - 1)) % MOD; combinationsDenominator = (combinationsDenominator * fact[segmentLength]) % MOD; } } // Last segment (after sick[sick.length - 1]) int lastSegmentLength = n - 1 - sick[sick.length - 1]; if (lastSegmentLength > 0) { combinationsDenominator = (combinationsDenominator * fact[lastSegmentLength]) % MOD; } long combinationsNumerator = fact[(int)totalUninfected]; long combinations = (combinationsNumerator * modInverse(combinationsDenominator)) % MOD; return (int) ((combinations * internalWays) % MOD); } private void precomputeFactorials(int n) { fact[0] = 1; for (int i = 1; i <= n; i++) { fact[i] = (fact[i - 1] * i) % MOD; } } private long power(long base, long exp) { long res = 1; base %= MOD; while (exp > 0) { if (exp % 2 == 1) res = (res * base) % MOD; base = (base * base) % MOD; exp /= 2; } return res; } private long modInverse(long n) { return power(n, MOD - 2); }}Complexity
Time
O(n + sick.length). Precomputing factorials takes O(n). The main loop over `sick` takes O(sick.length). Modular exponentiation takes O(log MOD), which is constant relative to n. Thus, the overall complexity is dominated by O(n).
Space
O(n) to store the precomputed factorials.
Trade-offs
Pros
Extremely efficient with linear time complexity, making it suitable for large inputs.
Provides a direct calculation, avoiding complex state management or recursion.
Elegant solution based on solid mathematical principles.
Cons
Requires knowledge of combinatorics (multinomial coefficients) and modular arithmetic (modular inverse, modular exponentiation).
The logic is less direct compared to a simulation, making it potentially harder to come up with initially.
Solutions
Solution
class Solution {private static final int MOD = (int)(1 e9 + 7);private static final int MX = 100000;private static final int[] FAC = new int[MX + 1]; static { FAC[0] = 1; for (int i = 1; i <= MX; i++) { FAC[i] = (int)((long)FAC[i - 1] * i % MOD); } }public int numberOfSequence(int n, int[] sick) { int m = sick.length; int[] nums = new int[m + 1]; nums[0] = sick[0]; nums[m] = n - sick[m - 1] - 1; for (int i = 1; i < m; i++) { nums[i] = sick[i] - sick[i - 1] - 1; } int s = 0; for (int x : nums) { s += x; } int ans = FAC[s]; for (int x : nums) { if (x > 0) { ans = (int)((long)ans * qpow(FAC[x], MOD - 2) % MOD); } } for (int i = 1; i < nums.length - 1; ++i) { if (nums[i] > 1) { ans = (int)((long)ans * qpow(2, nums[i] - 1) % MOD); } } return ans; }private int qpow(long a, long n) { long ans = 1; for (; n > 0; n >>= 1) { if ((n & 1) == 1) { ans = ans * a % MOD; } a = a * a % MOD; } return (int)ans; }}const int MX = 1e5 ; const int MOD = 1e9 + 7 ; int fac [ MX + 1 ]; auto init = [] { fac [ 0 ] = 1 ; for ( int i = 1 ; i <= MX ; ++ i ) { fac [ i ] = 1LL * fac [ i - 1 ] * i % MOD ; } return 0 ; }(); int qpow ( long long a , long long n ) { long long ans = 1 ; for (; n > 0 ; n >>= 1 ) { if ( n & 1 ) { ans = ( ans * a ) % MOD ; } a = ( a * a ) % MOD ; } return ans ; } class Solution { public: int numberOfSequence ( int n , vector < int >& sick ) { int m = sick . size (); vector < int > nums ( m + 1 ); nums [ 0 ] = sick [ 0 ]; nums [ m ] = n - sick [ m - 1 ] - 1 ; for ( int i = 1 ; i < m ; i ++ ) { nums [ i ] = sick [ i ] - sick [ i - 1 ] - 1 ; } int s = accumulate ( nums . begin (), nums . end (), 0 ); long long ans = fac [ s ]; for ( int x : nums ) { if ( x > 0 ) { ans = ans * qpow ( fac [ x ], MOD - 2 ) % MOD ; } } for ( int i = 1 ; i < nums . size () - 1 ; ++ i ) { if ( nums [ i ] > 1 ) { ans = ans * qpow ( 2 , nums [ i ] - 1 ) % MOD ; } } return ans ; } };mod = 10 ** 9 + 7 mx = 10 ** 5 fac = [ 1 ] * ( mx + 1 ) for i in range ( 2 , mx + 1 ): fac [ i ] = fac [ i - 1 ] * i % mod class Solution : def numberOfSequence ( self , n : int , sick : List [ int ]) -> int : nums = [ b - a - 1 for a , b in pairwise ([ - 1 ] + sick + [ n ])] ans = 1 s = sum ( nums ) ans = fac [ s ] for x in nums : if x : ans = ans * pow ( fac [ x ], mod - 2 , mod ) % mod for x in nums [ 1 : - 1 ]: if x > 1 : ans = ans * pow ( 2 , x - 1 , mod ) % mod return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.