Simulation using easy to follow code
Intuition\nSimulate the virus containment and spreading in a clear\nand easy to understand way. \n\n# Approach\nSimulates each tick of the containment and infec
# Intuition\nSimulate the virus containment and spreading in a clear\nand easy to understand way. \n\n# Approach\nSimulates each tick of the containment and infection, while tracking the virus that are not contained.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nimport Foundation\n\n\nclass Solution { // O(m*n)^2 + O(m*n) space\n    \n    enum CellStructure: Equatable {\n        case normal\n        case infected\n        case infectedWithID(UUID)\n        case contained\n        \n        init(_ integerValue: Int) {\n            self = (integerValue == 0) ? .normal : .infected\n        }\n        \n        var isInfected: Bool {\n            switch self {\n            case .infected, .infectedWithID: return true\n            default: return false\n            }\n        }\n        \n        var infectionId: UUID? {\n            switch self {\n            case .infectedWithID(let id): return id\n            default: return nil\n            }\n        }\n    }\n    \n    struct Point: Equatable, Hashable {\n        let x: Int\n        let y: Int\n        \n        init(_ x: Int, _ y: Int) {\n            self.x = x\n            self.y = y\n        }\n        \n        init(row: Int, column: Int) {\n            self.x = column\n            self.y = row\n        }\n        \n        var up: Point { Point(x, y - 1) }\n        var down: Point { Point(x, y + 1) }\n        var left: Point { Point(x - 1, y) }\n        var right: Point { Point(x + 1, y) }\n    }\n    \n    struct Infection: Equatable, Hashable, Comparable {\n        let id: UUID = UUID()\n        var cells: Set<Point>\n        var adjacentCells: Set<Point>\n        \n        static func <(lhs: Infection, rhs: Infection) -> Bool {\n            return lhs.adjacentCells.count < rhs.adjacentCells.count\n        }\n    }\n    \n    var body: [[CellStructure]] = [[CellStructure]]()\n    var walls: [Point] = []\n    var infections: [UUID: Infection] = [:]\n    \n    func containVirus(_ isInfected: [[Int]]) -> Int { // O(n*m)\n        \n        self.body = isInfected.map { row in row.map { CellStructure($0) } }\n                \n        infections = self.catalogInfections()\n        \n        while !infections.isEmpty {\n            \n            var sortedInfections = Array(infections.values).sorted(by: <) // O(k * log(k))\n            \n            if let infection = sortedInfections.popLast() {\n                self.infections[infection.id] = nil\n                var inspectedInfection = Set<Point>()\n                containInfection(infection.cells.first!, inspectedInfection: &inspectedInfection)\n            }\n            \n            var inspectedBody = Set<Point>()\n            \n            while var infection = sortedInfections.popLast() {\n                spreadInfection(&infection, inspectedBody: &inspectedBody)\n                if infection.cells.count > 0 {\n                    infections[infection.id] = infection\n                } else {\n                    infections[infection.id] = nil\n                }\n            }\n        }\n        \n        return walls.count\n    }\n    \n    private func catalogInfections() -> [UUID: Infection] { // O(m*n)\n        \n        let rows = body.count\n        let columns = body[0].count\n        \n        var inspectedBody: Set<Point> = []\n        \n        var infections: [UUID: Infection] = [:]\n        \n        for row in 0..<rows {\n            for column in 0..<columns {\n                let point = Point(row: row, column: column)\n                if body.containsPoint(point) && !inspectedBody.contains(point) && body.containsSpreadableInfection(atPoint: point) {\n                    var infection = Infection(cells: [], adjacentCells: [])\n                    findInfectionsAtPoint(point, inspectedBody: &inspectedBody, infection: &infection)\n                    infections[infection.id] = infection\n                }\n            }\n        }\n                \n        return infections\n    }\n    \n    private func containInfection(_ point: Point, inspectedInfection: inout Set<Point>) { // O(m*n)\n                        \n        guard body.containsPoint(point), !inspectedInfection.contains(point), body.containsSpreadableInfection(atPoint: point) else { return }\n            \n        inspectedInfection.insert(point)\n        body[point] = .contained\n        let adjacentCells = adjacentCells(point)\n        for adjacentCell in adjacentCells {\n            walls.append(adjacentCell)\n        }\n        \n        containInfection(point.left, inspectedInfection: &inspectedInfection)\n        containInfection(point.right, inspectedInfection: &inspectedInfection)\n        containInfection(point.up, inspectedInfection: &inspectedInfection)\n        containInfection(point.down, inspectedInfection: &inspectedInfection)\n    }\n    \n    private func spreadInfection(_ infection: inout Infection, inspectedBody: inout Set<Point>) { // O(m*n)\n                \n        inspectedBody.formUnion(infection.cells)\n        \n        for cell in infection.adjacentCells {\n            \n            if body.containsUninfectedCell(atPoint: cell) {\n                body[cell] = .infectedWithID(infection.id)\n                infection.cells.insert(cell)\n            }\n        }\n        \n        infection.adjacentCells.removeAll()\n        \n        for cell in infection.cells {\n            consumeInfection(cell.left, inspectedBody: &inspectedBody, infection: &infection)\n            consumeInfection(cell.right, inspectedBody: &inspectedBody, infection: &infection)\n            consumeInfection(cell.up, inspectedBody: &inspectedBody, infection: &infection)\n            consumeInfection(cell.down, inspectedBody: &inspectedBody, infection: &infection)\n        }\n        \n        for cell in infection.cells {\n            infection.adjacentCells.formUnion(self.adjacentCells(cell))\n        }\n    }\n    \n    private func consumeInfection(_ point: Point, inspectedBody: inout Set<Point>, infection: inout Infection) {\n        \n        guard body.containsPoint(point),\n              body.containsForeignInfection(atPoint: point, infectionID: infection.id), \n                let foreignInfectionID = self.body[point].infectionId,\n                let foreignInfection = self.infections[foreignInfectionID] else { return }\n        \n        defer {\n            infections[foreignInfectionID]?.adjacentCells.removeAll()\n            infections[foreignInfectionID]?.cells.removeAll()\n        }\n        \n        for cell in foreignInfection.cells {\n            body[cell] = .infectedWithID(infection.id)\n            infection.cells.insert(cell)\n            inspectedBody.insert(cell)\n        }\n        \n        if !inspectedBody.contains(point) {\n            for cell in infection.adjacentCells {\n                if body.containsUninfectedCell(atPoint: cell) {\n                    body[cell] = .infectedWithID(infection.id)\n                    infection.cells.insert(cell)\n                }\n            }\n        }\n    }\n\n    \n    private func findInfectionsAtPoint(_ point: Point, inspectedBody: inout Set<Point>, infection: inout Infection) {\n        \n        guard body.containsPoint(point), !inspectedBody.contains(point), body.containsSpreadableInfection(atPoint: point) else { return }\n        \n        inspectedBody.insert(point)\n        \n        body[point] = .infectedWithID(infection.id)\n        infection.cells.insert(point)\n        infection.adjacentCells.formUnion(adjacentCells(point))\n        \n        findInfectionsAtPoint(point.left, inspectedBody: &inspectedBody, infection: &infection)\n        findInfectionsAtPoint(point.right, inspectedBody: &inspectedBody, infection: &infection)\n        findInfectionsAtPoint(point.up, inspectedBody: &inspectedBody, infection: &infection)\n        findInfectionsAtPoint(point.down, inspectedBody: &inspectedBody, infection: &infection)\n    }\n    \n    private func adjacentCells(_ point: Point) -> [Point] {\n        \n        var adjacentCells: [Point] = []\n        if body.containsPoint(point.left), !body.containsInfection(atPoint: point.left) { adjacentCells.append(point.left) }\n        if body.containsPoint(point.right), !body.containsInfection(atPoint: point.right) { adjacentCells.append(point.right) }\n        if body.containsPoint(point.up), !body.containsInfection(atPoint: point.up) { adjacentCells.append(point.up) }\n        if body.containsPoint(point.down), !body.containsInfection(atPoint: point.down) { adjacentCells.append(point.down) }\n\n        return adjacentCells\n    }\n}\n\ntypealias CellStructure = Solution.CellStructure\n\nprivate extension Array where Element == [CellStructure] {\n    \n    /// Validates if the point is valid within this 2D Array\n    /// - Parameter point: A point to validate in the array\n    /// - Returns: `true` if the point is within the 2D Array\n    func containsPoint(_ point: Solution.Point) -> Bool {\n        guard point.x >= 0, point.y >= 0 else { return false }\n        guard point.y < self.count else { return false }\n        guard point.x < self[point.y].count else { return false }\n        \n        return true\n    }\n    \n    /// Validates if a point in the 2D array is infected\n    /// - Parameter point: A point to validate in the array\n    /// - Returns: `true` if the point is infected or `false` if the point is normal\n    func containsInfection(atPoint point: Solution.Point) -> Bool {\n        return self[point] != .normal\n    }\n    \n    func containsSpreadableInfection(atPoint point: Solution.Point) -> Bool {\n        return self[point].isInfected\n    }\n    \n    func containsUninfectedCell(atPoint point: Solution.Point) -> Bool {\n        return self[point] == .normal\n    }\n    \n    func containsForeignInfection(atPoint point: Solution.Point, infectionID: UUID) -> Bool {\n        switch self[point] {\n        case .infectedWithID(let id): return infectionID != id\n        default: return false\n        }\n    }\n    \n    subscript(index: Solution.Point) -> CellStructure {\n        get {\n            assert(containsPoint(index), "Index out of range")\n            return self[index.y][index.x]\n        }\n        set {\n            assert(containsPoint(index), "Index out of range")\n            self[index.y][index.x] = newValue\n        }\n    }\n    \n    var description: String {\n        var gridDescription = ""\n        \n        for row in self {\n            for cell in row {\n                switch cell {\n                case .normal:\n                    gridDescription += "N "  // \'N\' for Normal\n                case .infected:\n                    gridDescription += "I "  // \'I\' for Infected\n                case .contained:\n                    gridDescription += "C "  // \'C\' for Contained\n                case .infectedWithID(_):\n                    gridDescription += "I "  // \'I\' for Infected\n                }\n            }\n            gridDescription += "\\n"  // New line at the end of each row\n        }\n        \n        return gridDescription\n    }\n}\n\n```
['Swift']