Contain Virus

• Since you have already find the frontier element for a region in DFS(), you don't need to do it again in the containVirus() , just change those frontier element from 1 to 0 is okay.

• @yuryant I agreed with you.
see the following codes:

``````            #Triage the most infectious region, and spread the rest of the regions.
for i, reg in enumerate(regions):
if i == triage_index:
for r, c in reg:
grid[r][c] = -1
else:
for r, c in frontiers[i]:
grid[r][c] = 1
``````

it seems the above code is a little faster. but should be benchmarked.

• Why `viral regions that are alive must have size at least t^2 + (t-1)^2t`？ and why `the total number removed across all time is Ω(t^​3​​ )≤R∗C`?

• @FannyChung its wrong.
He is probably assuming that the viruses aren't bounded by the grid borders.
If grid is a line, say 1C, then viral region size at time t is at most O(t). So then we have up to O(C^(1/2)) iterations, and the time complexity is O(RC)^3/2.

To be fair, the input size is bounded by R, C < 50, so the worst case input size is where R == C, and for such a case, it is very plausible that, in the worst case, size of viral region is at time t is still O(t^2)

• @awice ,can you please explain why did you use the condition !seen.contains(r*C + c)) in if statement?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.