## Problem Simulate infection spread on a rectangular grid over a fixed number of days. Each cell is one of: - `S`: a susceptible person. - `I`: an infected person. - `M`: an immune person who cannot become infected. - `R`: a recovered person who cannot become infected again. - `.`: an empty cell. Every initially infected person and every newly infected person remains infected for exactly `recoveryDays` full simulation days. During each day, all currently infected people infect their orthogonally adjacent susceptible neighbors. The spread and all recoveries for a day are simultaneous: a person infected during day `d` begins spreading on day `d + 1`, and a person who completes their last infectious day may still spread during that day before becoming recovered. Return the grid after `days` days. ### Function Contract Implement `simulateInfection(grid, recoveryDays, days)` and return an array of strings representing the final grid. ### Constraints & Assumptions - `1 <= rows, columns` and `rows * columns <= 200,000`. - Every row has the same length and contains only `S`, `I`, `M`, `R`, and `.`. - `1 <= recoveryDays <= 200,000` and `0 <= days <= 200,000`. - Initial `I` cells begin with `recoveryDays` infectious days remaining. - Infection uses four-direction adjacency; diagonals do not spread disease. - Immune, recovered, and empty cells never change. ### Clarifying Questions to Ask - Do newly infected cells spread immediately? No, starting the following day. - Can a recovering cell infect neighbors on its final infectious day? Yes. - Can a recovered person be infected again? No. - Are updates simultaneous? Yes; traversal order must not affect the result. ```hint Separate today's sources from tomorrow's state Read all infection sources from the start-of-day state, collect susceptible targets, and apply those targets only after the day's spread decisions are complete. ``` ```hint Track remaining infectious days with the frontier The grid character alone cannot tell when an infected cell should recover. Maintain a recovery day or remaining-day value for each infected position. ``` ### Examples ```text grid = [ "SIS", "SMS", "SSS" ] recoveryDays = 2 days = 1 result = [ "III", "SMS", "SSS" ] ``` After a second day, the original center-top cell becomes `R`; cells infected on day one remain `I`, and the susceptible cells directly below the two top corners become infected. With `days = 0`, return the input state unchanged. ### Evaluation Focus - Uses simultaneous rather than in-place cascading infection. - Preserves immune, recovered, and empty cells. - Applies the stated first-spread and final-spread timing exactly. - Handles multiple sources targeting the same cell without duplicate work. - Runs in `O(rows * columns + processed infection events)` time without rescanning the full grid for every day. ### Extensions to Discuss 1. How would different recovery durations per person change the state representation? 2. How would the algorithm report the first day each cell became infected? 3. What changes if diagonal spread or walls are introduced?