Count the Number of Infection Sequences
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.
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 10^9+7.
Example 1
Input: n = 5, sick = [0,4]
Output: 4
Explanation: There is a total of 6 different sequences overall.
Example 2
Input: n = 4, sick = [1]
Output: 3
Explanation: There is a total of 6 different sequences overall.
Constraints
- 2 <= n <= 10^5
- 1 <= sick.length <= n - 1
- 0 <= sick[i] <= n - 1
- sick is sorted in increasing order.
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.