Simulation approach utilizing Union-Find to keep track of regions and BFS to expand a virus region.
Intuition\nWe will perform an actual simulation of the virus infection.\n\n# Approach\nThe logical approach isn\'t a complicated one, rather it\'s even presente
# Intuition\nWe will perform an actual simulation of the virus infection.\n\n# Approach\nThe logical approach isn\'t a complicated one, rather it\'s even presented in the problem statement:\n- Keep track of the virus regions\n- For each virus region, find the cells threatened by that region.\n    - all these cells will either be used to help build a border or they will be used to allow the virus to expand into them.\n- For the region which threatens the most unaffected cells, border it.\n- For all the other regions, expand into the threatened cells.\n- If any regions touch, they become one region.\n\nThe difficulty comes when deciding how to best represent the data, and it seems that UnionFind fits the bill decently (especially good at handling regions coming into contact). (but even so, it requires decent amount of coding).\n\n# Complexity\n- Time complexity:\n    - Union-find operations require O(1) amortized time.\n    - for each simulation day, we swipe once over the matrix with a BFS per region, total cumulating under O(m*n)\n    - initial number of regions can be O(m*n), but, without doing too much crazy math, it seems that the more regions there are, the faster they would connect, reducing fast the number of iterations.\n        - upper bound time complexity O(m^2*n^2), but in practice should be lower\n\n- Space complexity:\nO(m*n) since we\'re keeping track of the grid, the union-find forest, and the cumulated regional BFSes do not go over the size of the matrix.\n\n# Code\n```\nimport scala.collection._\nimport VirusQuarantine._\n\nobject Solution {\n    def containVirus(isInfected: Array[Array[Int]]): Int = {\n        val positions = (for {\n            r <- isInfected.indices\n            c <- isInfected(r).indices\n        } yield {\n            Position(r, c)\n        })\n        new VirusQuarantine(isInfected, positions).quarantine()\n    }\n}\n\nobject VirusQuarantine {\n    case class Position(r: Int, c: Int)\n\n    case class ThreatenedCells(virusCellThreat: Position, uninfectedCells: Seq[Position])\n\n    implicit class PositionOps(p: Position) {\n        def +(q: Position): Position = Position(p.r + q.r, p.c + q.c)\n    }\n\n    val Directions = Seq(Position(1, 0), Position(-1, 0), Position(0, 1), Position(0, -1))\n}\n\nclass VirusQuarantine(grid: Array[Array[Int]], positions: Seq[Position]) extends UnionFind[Position](positions) {\n    private val rows = grid.size\n    private val cols = grid(0).size\n\n    // init the union-find forest.\n    for {\n        r <- 0 until rows\n        c <- 0 until cols\n        p = Position(r, c)\n        if p.isInfected()\n    } {\n        if (c < cols - 1 && grid(r)(c + 1) == 1)\n            union(p)(Position(r, c + 1))\n        if (r < rows - 1 && grid(r + 1)(c) == 1)\n            union(p)(Position(r + 1, c))\n    }\n\n    def quarantine(): Int = {\n        var wallsCount = 0\n\n        val containedRegionsRoots = mutable.Set[Position]()\n\n        while (true) {\n            val uncontainedRegionsRoots = roots().filter(_.isInfected).toSet.diff(containedRegionsRoots)\n            \n            if (uncontainedRegionsRoots.isEmpty) return wallsCount\n\n            val threatenedCellsByRegion = uncontainedRegionsRoots.map(findThreatenedCells)\n            val maxCellCountThreatenedByOneRegion = threatenedCellsByRegion.map(_.uninfectedCells.size).max\n\n            val threatenedCellsToBorder = threatenedCellsByRegion.find(_.uninfectedCells.size == maxCellCountThreatenedByOneRegion).get\n            \n            val remainingUncontainedRegions = threatenedCellsByRegion - threatenedCellsToBorder\n            \n            wallsCount += border(threatenedCellsToBorder)\n            containedRegionsRoots += find(threatenedCellsToBorder.virusCellThreat)\n            \n            remainingUncontainedRegions.map(_.uninfectedCells.map(_.infect))\n        }\n\n        throw new IllegalStateException("unreachable statement")\n    }\n\n    private implicit class GridPositionOps(p: Position) {\n        def isWithinBounds(): Boolean = \n            0 <= p.r && p.r < rows && 0 <= p.c && p.c < cols\n\n        def isInfected(): Boolean = grid(p.r)(p.c) == 1\n\n        def infect(): Unit = {\n            grid(p.r)(p.c) = 1\n            getReachableNeighbors(p)\n                .filter(_.isInfected)\n                .foreach(union(p))\n        }\n    }\n\n    private def findThreatenedCells(infectedPosition: Position): ThreatenedCells = {\n        val root = find(infectedPosition)\n        val q = mutable.Queue[Position](root)\n        val vis = mutable.Set[Position](root)\n\n        val uninfectedCells = mutable.Set[Position]()\n\n        while (q.nonEmpty) {\n            val currPosition = q.dequeue()\n\n            val (virusNeighbors, uninfectedNeighbors) = \n                getReachableNeighbors(currPosition)\n                    .filterNot(vis.contains)\n                    .partition(_.isInfected)\n\n            q ++= virusNeighbors\n            vis ++= virusNeighbors\n\n            uninfectedCells ++= uninfectedNeighbors\n        }\n\n        ThreatenedCells(infectedPosition, uninfectedCells.toSeq)\n    }\n\n    private def border(threatenedCells: ThreatenedCells): Int =\n        threatenedCells.uninfectedCells.map { uninfectedCell =>\n            getReachableNeighbors(uninfectedCell).collect { \n                case neigh if find(neigh) == find(threatenedCells.virusCellThreat) => addBorder(neigh, uninfectedCell)\n            }.size\n        }.sum\n\n    private def getReachableNeighbors(p: Position): Seq[Position] = \n        Directions\n            .map(_ + p)\n            .filter(_.isWithinBounds)\n            .filterNot(isBorderPresent(p))\n\n    private val borders = mutable.Set[(Position, Position)]()\n    \n    def addBorder(a: Position, b: Position): Unit = borders ++= Set((a, b), (b, a))\n\n    def isBorderPresent(a: Position)(b: Position): Boolean = borders.contains((a, b))\n}\n\n\nclass UnionFind[T](collection: Iterable[T]) {\n\n    private val parent: mutable.Map[T, T] = collection.map(item => item -> item).to(mutable.Map)\n\n    def roots(): Set[T] = parent.keys.map(find).toSet\n\n    def union(a: T)(b: T): T = {\n        val aAncestor = find(a)\n        val bAncestor = find(b)\n        if (aAncestor != bAncestor) {\n            parent(aAncestor) = bAncestor\n        }\n        bAncestor\n    }\n\n    def find(a: T): T = {\n        val aParent = parent(a)\n        if (parent(a) != a) {\n            parent(a) = find(parent(a))\n        }\n        parent(a)\n    }\n}\n\n\n\n```
['Breadth-First Search', 'Union Find', 'Scala']