Brute Force approach

Time complexity: O(n²). Space complexity: O(1).

The brute force approach generates all possible sequences of infections and checks which ones are valid based on the infection rules. This is straightforward but inefficient as it considers all permutations.

The complexity is O(n²) because we generate all permutations of uninfected people, which is factorial in nature, and for each permutation, we check its validity in linear time.

1. Step 1: Generate all permutations of the uninfected people.
2. Step 2: For each permutation, check if it is a valid infection sequence by ensuring no uninfected person is infected before their adjacent infected person.
3. Step 3: Count the valid sequences and return the count modulo 10^9 + 7.

For n = 5, sick = [0, 4]: 1. Uninfected: [1, 2, 3] 2. Generate permutations: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1) 3. Check (1, 2, 3): Invalid (2 can't be infected before 1) 4. Check (1, 3, 2): Valid 5. Check (2, 1, 3): Invalid 6. Check (3, 2, 1): Valid Total valid sequences: 4.

Optimal Solution approach

Time complexity: Unknown. Space complexity: Unknown.

The optimal approach uses combinatorial mathematics to calculate the number of valid infection sequences based on the gaps between infected individuals. It leverages the fact that the order of infection in each segment is determined by the number of uninfected individuals adjacent to infected ones.

1. Step 1: Identify the segments of uninfected people between each pair of infected individuals.
2. Step 2: For each segment, calculate the number of ways to infect the uninfected individuals using combinations.
3. Step 3: Multiply the counts from all segments to get the total number of valid infection sequences.

Common Mistakes

• Relying too heavily on brute force without considering combinatorial approaches.
• Failing to account for edge cases, such as when sick individuals are at the boundaries.

Interview Tips

• Understand the problem constraints and how they affect your approach.
• Always consider edge cases and test your code with them.
• Practice explaining your thought process clearly, as communication is key in interviews.