Count the number of infection sequences

Array Math Combinatorics

37.3% acceptance

Feb 25, 2026

147

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. 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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_sequence(n: i32, sick: Vec<i32>) -> i32 {
    const MOD: u64 = 1_000_000_007;
    let n = n as usize;
    let sick: Vec<usize> = sick.iter().map(|&x| x as usize).collect();

    // Precompute factorials and inverse factorials
    let max_n = n + 1;
    let mut fact = vec![1u64; max_n];
    for i in 1..max_n {
      fact[i] = fact[i - 1] * i as u64 % MOD;
    }
    let mut inv_fact = vec![1u64; max_n];
    inv_fact[max_n - 1] = mod_pow(fact[max_n - 1], MOD - 2, MOD);
    for i in (0..max_n - 1).rev() {
      inv_fact[i] = inv_fact[i + 1] * (i + 1) as u64 % MOD;
    }

    fn mod_pow(mut base: u64, mut exp: u64, modulus: u64) -> u64 {
      let mut result = 1u64;
      base %= modulus;
      while exp > 0 {
        if exp & 1 == 1 { result = result * base % modulus; }
        base = base * base % modulus;
        exp >>= 1;
      }
      result
    }

    // Collect segment sizes
    let mut segments: Vec<(usize, bool)> = Vec::new(); // (size, is_interior)
    let s = sick.len();

    // Left boundary
    if sick[0] > 0 {
      segments.push((sick[0], false));
    }
    // Interior segments
    for i in 0..s - 1 {
      let gap = sick[i + 1] - sick[i] - 1;
      if gap > 0 {
        segments.push((gap, true));
      }
    }
    // Right boundary
    if sick[s - 1] < n - 1 {
      segments.push((n - 1 - sick[s - 1], false));
    }

    // Total uninfected
    let u: usize = segments.iter().map(|&(sz, _)| sz).sum();

    let mut ans = fact[u];
    for &(sz, is_interior) in &segments {
      ans = ans * inv_fact[sz] % MOD;
      if is_interior && sz > 1 {
        ans = ans * mod_pow(2, (sz - 1) as u64, MOD) % MOD;
      }
    }

    ans as i32
  }
}