Paint the picture
For each 1 in the grid, we paint all connected 1 with the next available color (2, 3, and so on).\n\nWe also remember the size of the island we just painted wit
For each ```1``` in the grid, we paint all connected ```1``` with the next available color (2, 3, and so on).\n\nWe also remember the size of the island we just painted with that color.\n\nThen, we analyze all ```0``` in the grid, and sum sizes of connected islands (based on the island color). \n\n> Note that the same island can connect to  ```0``` more than once.\n \nThe picture below demonstrates this idea (the answer is highlighted):\n<p align="center">\n  <img src="https://s3-lc-upload.s3.amazonaws.com/users/votrubac/image_1525310120.png">\n</p>\n\n**C++**\n```cpp\nint get(int i, int j, vector<vector<int>>& g) {\n  return (min(i, j) < 0 || i >= g.size() || j >= g[0].size()) ? 0 : g[i][j];\n}\nint paint(int i, int j, int clr, vector<vector<int>>& g) {\n  if (get(i, j, g) != 1)\n    return 0;\n  g[i][j] = clr;\n  return 1 + paint(i + 1, j, clr, g) + paint(i - 1, j, clr, g) +\n             paint(i, j + 1, clr, g) + paint(i, j - 1, clr, g);\n}\nint largestIsland(vector<vector<int>>& g, int res = 0) {\n  vector<int> sizes = {0, 0};  // sentinel values; colors start from 2.\n  for (auto i = 0; i < g.size(); ++i)\n    for (auto j = 0; j < g[i].size(); ++j)\n      if (g[i][j] == 1)\n\t    sizes.push_back(paint(i, j, sizes.size(), g));\n  for (auto i = 0; i < g.size(); ++i)\n    for (auto j = 0; j < g[i].size(); ++j)\n      if (g[i][j] == 0) {\n        unordered_set<int> s = { get(i + 1, j, g), get(i - 1, j, g),\n                                 get(i, j + 1, g), get(i, j - 1, g) };\n        res = max(res, accumulate(begin(s), end(s), 1, [&](int sum, int col) {\n          return sum + sizes[col];\n        }));\n      }\n  return res == 0 ? g.size() * g[0].size() : res;\n}\n```\nJust to compare, below is a brute-force solution (accepted) that calculates the size of an island after flipping ```0```. It\'s  shorter, but runtime is above 400 ms. It would probably be a good idea so stick to a simpler solution to save time during contests.\n\n> Update: the runtime of this solution is close to 2,000 ms now. \n\n**C++**\n```cpp\nint paint(int i, int j, int c, vector<vector<int>>& g, bool flip = false) {\n  if (!flip && (min(i, j) < 0 || i >= g.size() || j >= g[0].size() ||\n                g[i][j] == 0 || g[i][j] == c))\n    return 0;\n  g[i][j] = g[i][j] == 0 ? 0 : c;\n  return 1 + paint(i + 1, j, c, g) + paint(i - 1, j, c, g) +\n         paint(i, j + 1, c, g) + paint(i, j - 1, c, g);\n}\nint largestIsland(vector<vector<int>>& g, int res = 0) {\n  for (int i = 0; i < g.size(); ++i)\n    for (int j = 0; j < g[i].size(); ++j)\n      if (g[i][j] == 0) {\n        res = max(res, paint(i, j, 2, g, true));\n        paint(i, j, 1, g, true);\n      }\n  return res == 0 ? g.size() * g[0].size() : res;\n}\n```
['C']