Katkat
Back

Count Valid Infection Orders

UberSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to use combinatorial counting and dynamic programming to determine the number of valid sequences in which a population can be infected under specific adjacency constraints.

Problem Statement

In a research lab, there are n subjects lined up in a row. Initially, everyone is healthy. An infection starts at one subject, and at each step, an infection can spread to an adjacent healthy neighbor. Specifically, if a set of subjects is already infected, the next person to become infected must be a healthy neighbor of someone who is already infected.

Given an integer n (the number of subjects), calculate the total number of distinct sequences in which all n subjects can become infected.

Since the result can be very large, return your answer modulo 10^9 + 7.

Example 1

Input: n = 3 Output: 4 Explanation: Let the subjects be 1, 2, 3.

  • Start at 1: (1, 2, 3)
  • Start at 2: (2, 1, 3) and (2, 3, 1)
  • Start at 3: (3, 2, 1) Total valid sequences: 4.

Constraints

  • 1 int.

Edge Cases

  • Consider n = 1 (the only sequence is (1)).
  • Verify if the logic holds for small n where the growth of possibilities is exponential.

Hints

Hint 1

Notice that at any step, the set of infected people must form a single contiguous block.

Hint 2

Consider the state as defined by the range `[left, right]` representing the currently infected indices in the row.

Hint 3

Observe that each new person infected must be adjacent to the existing contiguous block, effectively expanding the range by one position at either end.

Follow-up questions

  • How does the complexity change if some subjects are immune and cannot be infected, acting as barriers?
  • If you had to return the actual list of all valid infection sequences instead of just the count, what would be the time complexity?
  • Can this problem be solved using a closed-form combinatorial formula instead of dynamic programming?