BEST C++ SOLUTION WITH 41MS OF RUNTIME !
\n# Code\n\nstruct Region {\n  // Given m = the number of rows and n = the number of columns, (x, y) will be\n  // hashed as x * n + y.\n  unordered_set<int> in
\n# Code\n```\nstruct Region {\n  // Given m = the number of rows and n = the number of columns, (x, y) will be\n  // hashed as x * n + y.\n  unordered_set<int> infected;\n  unordered_set<int> noninfected;\n  int wallsRequired = 0;\n};\n\nclass Solution {\n public:\n  int containVirus(vector<vector<int>>& isInfected) {\n    const int m = isInfected.size();\n    const int n = isInfected[0].size();\n    int ans = 0;\n\n    while (true) {\n      vector<Region> regions;\n      vector<vector<bool>> seen(m, vector<bool>(n));\n\n      for (int i = 0; i < m; ++i)\n        for (int j = 0; j < n; ++j)\n          if (isInfected[i][j] == 1 && !seen[i][j]) {\n            Region region;\n            // Use DFS to find all the regions (1s).\n            dfs(isInfected, i, j, region, seen);\n            if (!region.noninfected.empty())\n              regions.push_back(region);\n          }\n\n      if (regions.empty())\n        break;  // No region causes further infection.\n\n      // Regions that infect the most neighbors will be sorted to the back of\n      // the array.\n      ranges::sort(regions, [](const Region& a, const Region& b) {\n        return a.noninfected.size() < b.noninfected.size();\n      });\n\n      // Build walls around the region that infects the most neighbors.\n      Region mostInfectedRegion = regions.back();\n      regions.pop_back();\n      ans += mostInfectedRegion.wallsRequired;\n\n      for (const int neighbor : mostInfectedRegion.infected) {\n        const int i = neighbor / n;\n        const int j = neighbor % n;\n        // The isInfected is now contained and won\'t be infected anymore.\n        isInfected[i][j] = 2;\n      }\n\n      // For remaining regions, infect their neighbors.\n      for (const Region& region : regions)\n        for (const int neighbor : region.noninfected) {\n          const int i = neighbor / n;\n          const int j = neighbor % n;\n          isInfected[i][j] = 1;\n        }\n    }\n\n    return ans;\n  }\n\n private:\n  void dfs(const vector<vector<int>>& isInfected, int i, int j, Region& region,\n           vector<vector<bool>>& seen) {\n    if (i < 0 || i == isInfected.size() || j < 0 || j == isInfected[0].size())\n      return;\n    if (seen[i][j] || isInfected[i][j] == 2)\n      return;\n    if (isInfected[i][j] == 0) {\n      region.noninfected.insert(i * isInfected[0].size() + j);\n      ++region.wallsRequired;\n      return;\n    }\n\n    // isInfected[i][j] == 1\n    seen[i][j] = true;\n    region.infected.insert(i * isInfected[0].size() + j);\n\n    dfs(isInfected, i + 1, j, region, seen);\n    dfs(isInfected, i - 1, j, region, seen);\n    dfs(isInfected, i, j + 1, region, seen);\n    dfs(isInfected, i, j - 1, region, seen);\n  }\n};\n```
['C++']