# Count the Number of Infection Sequences
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-the-number-of-infection-sequences)
Canonical: https://scaleengineer.com/dsa/problems/count-the-number-of-infection-sequences
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics)
**Data structures:** Array
**Companies:** [SAP](https://scaleengineer.com/companies/sap), [Tekion](https://scaleengineer.com/companies/tekion)
---
## Problem
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 <= 105`
* `1 <= sick.length <= n - 1`
* `0 <= sick[i] <= n - 1`
* `sick` is sorted in increasing order.

# Approaches
## Brute-Force Simulation with Backtracking
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.
**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`.
**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 `n` due to deep recursion.; Requires memoization to be even slightly feasible, but the state space (2^n) is too large to memoize effectively.
### Explanation
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:
1.  Infect person 1. The new infected set is `{0, 1, 4}`. Recurse from this state.
2.  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.

```java
// 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;
    }
}
```
### 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 `sick` array.
- **Base Case:** If the size of `infectedSet` equals `n`, 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 in `infectedSet`.
  - Initialize a counter for the number of sequences, `count = 0`.
  - For each `candidate`:
    - Add the `candidate` to a temporary `infectedSet`.
    - Recursively call `countSequences` with the new set and add the result to `count`.
    - Backtrack by removing the `candidate` (this step is implicitly handled by passing new sets or creating copies).
- Return the total `count`, ensuring all additions are performed modulo `10^9 + 7`.

## Combinatorial Analysis with Precomputation
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:
1.  The number of ways to determine the infection order *within* each segment.
2.  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.
**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.
**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.
### Explanation
This approach breaks the problem down into smaller, independent parts that can be solved with combinatorial formulas.

**1. Segments and Internal Orderings**
- The `sick` array 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 `k` between two infected groups (e.g., `[3,4,5,6]`) can be infected from either the left or the right. For the first `k-1` infections within this segment, there are always two choices. This results in **`2^(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 is `T = k_1 + k_2 + ... + k_m`.
- We have `T` total infection steps to perform. The problem is equivalent to arranging `T` items where there are `k_1` of type 1, `k_2` of 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.

```java
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);
    }
}
```
### Algorithm
- **Step 1: Precompute Factorials.** Calculate factorials up to `n` modulo `10^9 + 7` to 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]` and `sick[i]`: `sick[i] - sick[i-1] - 1`.
  - Segment after the last sick person: `n - 1 - sick[sick.length - 1]`.
- **Step 3: Calculate Internal Orderings.** For each segment of length `k` that is between two sick groups, there are `2^(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 is `T`, the number of ways to interleave them is given by the multinomial coefficient `T! / (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.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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 ; } };
```

### Python

```python
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 ans
```