Count the Number of Infection Sequences - Practice Coding Problems

Count the Number of Infection Sequences - 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 (positions 0 to n-1).

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 10^9 + 7.

Input & Output

Example 1 — Basic Internal Segment

$ Input: n = 5, sick = [0,4]

› Output: 4

💡 Note: Uninfected people are [1,2,3]. Person 1 can only be infected by 0, and person 3 can only be infected by 4. Person 2 can be infected by either 1 or 3, creating multiple valid sequences: [1,2,3], [1,3,2], [2,1,3], [3,2,1].

Example 2 — Single Gap

$ Input: n = 4, sick = [1,3]

› Output: 2

💡 Note: Uninfected people are [0,2]. Position 0 can only be infected by 1, position 2 can only be infected by 3. Valid sequences: [0,2] and [2,0].

Example 3 — All Initially Sick

$ Input: n = 3, sick = [0,1,2]

› Output: 1

💡 Note: Everyone is already infected, so there's only one empty sequence (no one to infect).

Constraints

2 ≤ n ≤ 10⁵
1 ≤ sick.length ≤ n
0 ≤ sick[i] ≤ n - 1
sick is sorted in increasing order

Visualization

Tap to expand

Understanding the Visualization

Initial State

Some people are initially infected (sick array)

Spreading Rules

Infection spreads only to adjacent uninfected people

Count Sequences

Find all possible orders of infection

Key Takeaway

🎯 Key Insight: Infection spreads in independent segments between initially sick people, each with 2^(gap-1) possible sequences

Asked in

G Google 12 f Meta 8 a Amazon 6

The key insight is that infection spreads in segments between initially infected people. Each internal segment of size k can be filled in 2^(k-1) ways. The optimal approach uses combinatorics to count sequences mathematically instead of generating them. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming with Combinatorics	O(n)	O(1)	Use math to count infection sequences for each segment between sick people
Brute Force - Try All Sequences	O((n-k)!)	O(n)	Generate all possible infection sequences and count valid ones

Dynamic Programming with Combinatorics — Algorithm Steps

Identify segments between infected people
For each segment, calculate ways to infect from both ends
Use factorials and combinations to count sequences
Multiply results for all segments

Visualization

Tap to expand

Step-by-Step Walkthrough

Identify Segments

Find gaps between initially infected people

Calculate Ways

Each internal gap has 2^(gap-1) ways to fill

Multiply Results

Independent segments multiply together

Final Count

Product gives total infection sequences

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007
#define MAX_N 100

long long modPow(long long base, long long exp, long long mod) {
    long long result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        exp = exp / 2;
        base = (base * base) % mod;
    }
    return result;
}

int solution(int n, int* sick, int sickSize) {
    if (sickSize == n) return 1;
    
    long long result = 1;
    
    // Handle segments between consecutive sick people
    for (int i = 0; i < sickSize - 1; i++) {
        int left = sick[i];
        int right = sick[i + 1];
        int gap = right - left - 1;
        
        if (gap > 0) {
            long long ways = modPow(2, gap - 1, MOD);
            result = (result * ways) % MOD;
        }
    }
    
    return (int)result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[1000];
    scanf(" %s", line);
    
    int sick[MAX_N];
    int sickSize = 0;
    
    if (strlen(line) > 2) {
        char* token = strtok(line + 1, ",]");
        while (token != NULL) {
            sick[sickSize++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    printf("%d\n", solution(n, sick, sickSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to identify segments and calculate factorials

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables for calculations

✓ Linear Space

8.8K Views

Medium Frequency

~35 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming with Combinatorics — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler