Another Explanation, Python3, O(R*C*max(R,C)) time and O(R*C) space, Faster than 95%
Intuition\n Describe your first thoughts on how to solve this problem. \n\nThis is a pretty hard problem, there\'s a lot going on. There are a lot of considerat
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nThis is a pretty hard problem, there\'s a lot going on. There are a lot of considerations to make. But the idea is that the problem asks us to wall of clusters according to what happens each day/night, and explains the rules. So we simulate.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nI didn\'t come up with the solution, but thought that the existing solutions are kind of hard to read and understand what they\'re doing. So I made a `Cluster` structure and `findCluster` method to help break things up. The main loop is a lot easier to read after that.\n\nAs the problem says, for each day/night cycle:\n1. during the day, we find the cluster that threatens the most cells, then wall it off\n2. at night, the remaining cluster(s) expand by 1 in each cardinal direction\n\nSo to break it down, we need the following\n1. we need to identify all of the clusters\n2. for each cluster we need to know the cells in that cluster so we can wall it off, the adjacent healthy cells so we know how many there are, and the number of walls required to wall it off\n\nWhen we wall off a cluster, we set all of its cells to some marker value `-1`. Originally I struggled with marking off only the boundary to be more efficient. But that was making the solution too complicated so I simplified and just marked them all off.\n\nFollowing another solution, I made a little `Cluster` class that contains the details.\n\n**NOTE:** I struggled a lot initially because I tried to be fancy about unioning `Cluster`s together to avoid re-finding clusters at each step. Eventually I gave up because it was getting to complicated.\n\nTo make it work I\'d use something along the lines of union-find:\n* have an array that maps (r,c) to the index of the cluster containing it\n* have the usual findRoot and union methods of union-find to quickly unify clusters each night when they expand\n  * having a set of coordinates for adjacent cells is easy to union: just merge the cells\n  * to merge the number of walls, that\'s more complicated and where I started getting really confused. There\'s probably a simple expression after working through all the edge cases though\n\nIn the end, if all the complications are worked out and you only track boundary cells, the complexity of the solution problably drops to $O((R+C)*\\max(R,C))$.\n\n# Complexity\n- Time complexity: $$O(R*C*\\max(R,C)))$$\n\nI think that\'s right but I\'m not sure. The worst-case scenario is we have a bunch of isolated little clusters so we need a lot of iterations. The most iterations we will do is order $\\max(R,C)$ since clusters can\'t grow for more than that number of steps. In each iteration we do $O(R*C)$ work to find all the clusters.\n\n\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(R*C)$$\n\nAt worst we store every infected cell in 1 `Cluster`, and every healthy cel in 4 `Cluster`s. We also have the `visited` array with $R*C$ entries. So overall it\'s order $R*C$.\n\n# Code\n```\nclass Solution:\n    def containVirus(self, isInfected: List[List[int]]) -> int:\n        # ruh-roh...\n\n        #   each night we want to find\n        #     (1) all of the clusters\n        #           cells in the cluster\n        #           adjacent healthy cells\n        #           number of adjoining walls\n        #     (2) order clusters by num adjacent healthy cells\n        #     (3) pick cluster with most healthy cells\n\n        R = len(isInfected)\n        C = len(isInfected[0])\n\n        class Cluster:\n            def __init__(self):\n                self.cells = set() # (r,c) of all infected cells in here\n                self.risked = set() # (r,c) of all adjacent healthy cells\n                self.walls = 0 # number of walls required to fence of this cluster\n\n            def numRisked(self):\n                return len(self.risked)\n\n            def __repr__(self):\n                return "Cluster(%i cells, %i risked, %i walls)" % (len(self.cells), len(self.risked), self.walls)\n\n        fenced = -1\n\n        def getCluster(i: int, j: int, visited: list[list[bool]]) -> \'Cluster\':\n            cluster = Cluster()\n            stack = [(i,j)]\n            visited[i][j] = True\n            while stack:\n                (r,c) = stack.pop()\n                cluster.cells.add((r,c))\n\n                for dr,dc in [(-1,0), (+1,0), (0,-1), (0,+1)]:\n                    rr = r + dr\n                    cc = c + dc\n                    if rr >= 0 and rr < R and cc >= 0 and cc < C:\n                        if visited[rr][cc]:\n                            continue\n                        \n                        # not visited: is healthy or fenced off or infected\n                        if isInfected[rr][cc] == 1:\n                            # infected: add to stack and visited\n                            stack.append((rr,cc))\n                            visited[rr][cc] = True\n                        elif isInfected[rr][cc] == 0:\n                            # healthy\n                            cluster.walls += 1 # there\'s a border between (r,c) and (rr,cc)\n                            # print("  added wall between", (r,c), (rr,cc))\n                            cluster.risked.add((rr,cc))\n\n            return cluster\n\n        # when are we done? when there are no clusters\n        # if there\'s one big cluster at the end (all infected), then number of fences will be zero because evrything is either\n        # a fence for a boundary already\n\n        walls = 0\n\n        while True:\n            clusters = []\n            visited = [[False]*C for _ in range(R)]\n            for r in range(R):\n                for c in range(C):\n                    if isInfected[r][c] == 1 and not visited[r][c]:\n                        clusters.append(getCluster(r,c,visited))\n\n            if not clusters:\n                return walls\n\n            # print(clusters)\n            clusters.sort(key=lambda cluster: cluster.numRisked())\n\n            # wall off the cluster that threatens the most cells\n            walls += clusters[-1].walls\n\n            # mark those cells as walled-off for the sake of later getCluster calls\n            for (r,c) in clusters[-1].cells:\n                isInfected[r][c] = -1\n\n            # grow all other clusters\n            clusters.pop()\n            for cluster in clusters:\n                for (r,c) in cluster.risked:\n                    isInfected[r][c] = 1\n```
['Python3']