Contain Virus

  • 0

    Click here to see the full article post

  • 0

    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.

  • 0

    @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
                        for r, c in frontiers[i]:
                            grid[r][c] = 1

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

  • 0

    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?

  • 0

    @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)

  • 0

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

Log in to reply

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