Problem Explanation:

We are given a 2-dimensional grid of 0's and 1's where 1 represents land and 0 represents water. A group of 1's represent an island, and islands are only 4-directionally connected that is, up, down, right, left. Our task is that we can flip at most one 0 to 1 so as to form the largest possible island. We need to output the size of the largest island after performing such operation.

Let's consider an example: [[1, 0], [0, 1]] Here, we have 2 islands each of size 1. However, there is a 0 between these islands. If we flip this 0 to 1, these 2 islands will connect forming a larger island of size 3. Hence the output in this case will be 3.

Solution Explanation:

One way to approach this problem is by using depth-first search (DFS) and coloring. First we scan through the entire grid and color each island (group of connected 1's) using DFS and keep track of the size of each island in a sizes array.

Next, we again scan through the grid and for every water cell (a, b) (cell with 0), we look at the neighboring cells (up, down, left, right). If we find any neighboring land cells, we get their island id's (color) and add up their sizes and update our maxSize variable if it becomes greater upon flipping the current water cell.

By the end of these operations, maxSize will contain the size of the largest island that can be formed.

Example:

Let's assume the grid is

1
2
3[[1, 0, 0, 0],
4 [0, 1, 0, 1],
5 [0, 0, 1, 0],
6 [0, 0, 0, 1]].

In the initial DFS, the islands are colored as

1
2
3[[2, 0, 0, 0],
4 [0, 3, 0, 4],
5 [0, 0, 3, 0],
6 [0, 0, 0, 5]]. 
7

And sizes array becomes [0, 0, 1, 2, 1, 1] (indices represent the colored id and values represent the size of each colored id).

Next, we iterate through the grid cells. For each water cell, we calculate the size of the island if we flip the current water cell. After all operations, we get the largest island size as 4 (upon flipping the [2][1] cell).

Python Solution:

1
2python
3
4class Solution:
5    def paint(self, grid, r, c, id):
6        if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]) or grid[r][c] != 1:
7            return 0
8        grid[r][c] = id
9        return (1 + self.paint(grid, r + 1, c, id) + self.paint(grid, r - 1, c, id) +  
10               self.paint(grid, r, c - 1, id) + self.paint(grid, r, c + 1, id))
11
12    def largestIsland(self, grid):
13        sizes = {0: 0}
14        id = 2
15        for r in range(len(grid)):
16            for c in range(len(grid[0])):
17                if grid[r][c] == 1:
18                    sizes[id] = self.paint(grid, r, c, id)
19                    id += 1
20        ans = max(sizes.values() or [0])
21        for r, row in enumerate(grid):
22            for c, val in enumerate(row):
23                if val == 0:
24                    seen = {grid[r + dr][c + dc] for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)) if 0 <= r + dr < len(grid) and 0 <= c + dc < len(grid[0])}
25                    ans = max(ans, sum(sizes[i] for i in seen) + 1)
26        return ans

Java solution:

1
2java
3class Solution {
4    public int largestIsland(int[][] grid) {
5        int N = grid.length;
6        int[] size = new int[N*N];
7        int t = 2;  // color
8
9        for (int r = 0; r < N; ++r)
10            for (int c = 0; c < N; ++c)
11                if (grid[r][c] == 1)
12                    size[t] = dfs(grid, r, c, t++);
13        int ans = 0;
14        for (int x: size)
15            ans = Math.max(ans, x);
16
17        for (int r = 0; r < N; ++r)
18            for (int c = 0; c < N; ++c)
19                if (grid[r][c] == 0){
20                    HashSet<Integer> seen = new HashSet<>();
21                    for (int i = 0; i < 4; ++i){
22                        int nr = r + dr[i];
23                        int nc = c + dc[i];
24                        if (0 <= nr && nr < N && 0 <= nc && nc < N)
25                            if (grid[nr][nc] > 1)
26                                seen.add(grid[nr][nc]);
27                    }
28                    int bns = 1;
29                    for (int i: seen) bns += size[i];
30                    ans = Math.max(ans, bns);
31                }
32        return ans;
33    }
34
35    int[] dr = new int[]{1, 0, -1, 0};
36    int[] dc = new int[]{0, 1, 0, -1};
37    public int dfs(int[][] grid, int r, int c, int t){
38        int N = grid.length;
39        int ret = 1;
40        grid[r][c] = t;
41        for (int i = 0; i < 4; ++i){
42            int nr = r + dr[i];
43            int nc = c + dc[i];
44            if (0 <= nr && nr < N && 0 <= nc && nc < N)
45                if (grid[nr][nc] == 1)
46                    ret += dfs(grid, nr, nc, t);
47        }
48        return ret;
49    }
50}

JavaScript solution:

1
2javascript
3var largestIsland = function(grid) {
4    var rank = [];
5    var parent = [];
6    var gridCellToIslandIdMapping = [];
7    var islandId = 1;
8    var rows =  grid.length;
9    var cols = grid[0].length;
10    for(var i = 0; i < rows; i++) {
11        for(var j = 0; j < cols; j++) {
12            if(grid[i][j] === 1) {
13                gridCellToIslandIdMapping[`${i}${j}`] = islandId;
14                parent[islandId] = islandId;
15                rank[islandId] = 1;
16                computeRankAndParent(grid, i, j, islandId, gridCellToIslandIdMapping, rank, parent);
17                islandId++;
18            }
19        }
20    }
21    var maxArea = Math.max.apply(null, rank);
22    for(var i = 0; i < rows; i++) {
23        for(var j = 0; j < cols; j++) {
24            if(grid[i][j] === 0) {
25                var uniqueParents = new Set();
26                if(i-1 >=0 && grid[i-1][j] === 1) {
27                    var islandId = gridCellToIslandIdMapping[`${i-1}${j}`];
28                    uniqueParents.add(find(parent, islandId));
29                }
30                 if(j-1 >=0 && grid[i][j-1] === 1) {
31                     var islandId = gridCellToIslandIdMapping[`${i}${j-1}`];
32                     uniqueParents.add(find(parent, islandId));
33                }
34                if(i+1 < rows && grid[i+1][j] === 1) {
35                    var islandId = gridCellToIslandIdMapping[`${i+1}${j}`];
36                    uniqueParents.add(find(parent, islandId));
37                }
38                if(j+1 < cols && grid[i][j+1] === 1) {
39                    var islandId = gridCellToIslandIdMapping[`${i}${j+1}`];
40                    uniqueParents.add(find(parent, islandId));
41                }
42                var area =0;
43                uniqueParents.forEach((item) => {area += rank[item]});
44                maxArea = Math.max(maxArea, 1+ area);
45            }
46        }
47    }
48    return maxArea;
49};
50
51var computeRankAndParent = function(grid, row, col, islandId,  gridCellToIslandIdMapping, rank, parent) {
52      var rows =  grid.length;
53      var cols = grid[0].length;
54      var directions = [[-1,0], [1,0], [0,-1],[0,1]];
55      for(var i=0; i < directions.length; i++) {
56          var newRow = row + directions[i][0];
57          var newCol = col + directions[i][1];
58          if(isValidCell(newRow, newCol, rows, cols) && grid[newRow][newCol] === 1 &&  gridCellToIslandIdMapping[`${newRow}${newCol}`] === undefined) {
59            union(parent, rank, islandId, islandId);
60            gridCellToIslandIdMapping[`${newRow}${newCol}`] = islandId;
61            computeRankAndParent(grid, newRow, newCol, islandId, gridCellToIslandIdMapping, rank, parent);
62          }
63      }
64}
65
66var isValidCell = function(row, col, rows, cols) {
67    if(row < 0 || row >= rows || col < 0 || col >= cols) {
68        return false;
69    }
70    return true;
71}
72
73var find = function(parent, i) {
74    if(parent[i] !== i) {
75        parent[i] = find(parent, parent[i]);
76    }
77    return parent[i];
78}
79
80var union = function(parent, rank, x, y) {
81    var xSet = find(parent, x);
82    var ySet = find(parent, y);
83    if(xSet !== ySet) {
84        if(rank[xSet] < rank[ySet]) {
85            parent[xSet] = ySet;
86            rank[ySet]++;
87        } else {
88            parent[ySet] =  xSet;
89            rank[xSet]++;
90        }    
91    }
92}

C++ solution:

1
2c++
3class Solution {
4public:
5    int largestIsland(vector<vector<int>>& grid) {
6        int m = grid.size(), n = grid[0].size(), res = 0, cur = 2, offset[] = {0, 1, 0, -1, 0}; 
7        unordered_map<int, int> area;
8        for (int i = 0; i < m; ++i) {
9            for (int j = 0; j < n; ++j) {
10                if (grid[i][j] == 1) {
11                    area[cur] = getArea(grid, i, j, cur++);
12                    res = max(res, area[cur]);
13                }
14            }
15        }
16        for (int i = 0; i < m; ++i) {
17            for (int j = 0; j < n; ++j) {
18                if (grid[i][j] == 0) {
19                    unordered_set<int> s;
20                    for (int k = 0; k < 4; ++k) {
21                        int x = i + offset[k], y = j + offset[k + 1];
22                        if (x >= 0 && x < m && y >= 0 && y < n) {
23                            s.insert(grid[x][y]);
24                        }
25                    }
26                    int plus = 1;
27                    for (auto a : s) {
28                        plus += area[a];
29                    }
30                    res = max(res, plus);
31                }
32            }
33        }
34        return res;
35    }
36    int getArea(vector<vector<int>>& grid, int i, int j, int cur) {
37        int m = grid.size(), n = grid[0].size(), res = 0, offset[] = {0, 1, 0, -1, 0};
38        grid[i][j] = cur;
39        for (int k = 0; k < 4; ++k) {
40            int x = i + offset[k], y = j + offset[k + 1];
41            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
42                res += getArea(grid, x, y, cur);
43            }
44        }
45        return res + 1;
46    }
47};

C# solution:

1
2csharp
3public class Solution {
4    public int LargestIsland(int[][] grid) {
5        int N = grid.Length;
6        int[][] dirs = new int[][]{new int[]{0,1}, new int[]{1,0}, new int[]{0,-1}, new int[]{-1,0}};
7        int[] area = new int[N*N + 2];
8        int id = 2;
9        int res = 0;
10        for (int i = 0; i < N; i++)
11            for (int j = 0; j < N; j++)
12                if (grid[i][j] == 1) {
13                    area[id] = getArea(grid, i, j, id++);
14                    res = Math.Max(res, area[id-1]);
15                }
16        for (int i = 0; i < N; i++)
17            for (int j = 0; j < N; j++)
18                if (grid[i][j] == 0) {
19                    HashSet<int> hs = new HashSet<int>();
20                    foreach (int[] dir in dirs) {
21                        int x = i + dir[0], y = j + dir[1];
22                        if (x < 0 || x >= N || y < 0 || y >= N || grid[x][y] == 0) continue;
23                        hs.Add(grid[x][y]);
24                    }
25                    int temp = 1;
26                    foreach (int k in hs) temp += area[k];
27                    res = Math.Max(res, temp);
28                }
29        return res;
30    }
31    public int getArea(int[][] grid, int i, int j, int id) {
32        int N = grid.Length;
33        int res = 1;
34        grid[i][j] = id;
35        int[][] dirs = new int[][]{new int[]{0,1}, new int[]{1,0}, new int[]{0,-1}, new int[]{-1,0}};
36        foreach (int[] dir in dirs) {
37            int x = i + dir[0], y = j + dir[1];
38            if (x < 0 || x >= N || y < 0 || y >= N || grid[x][y] != 1) continue;
39            res += getArea(grid, x, y, id);
40        }
41        return res;
42    }
43}

These are the basic ideas behind the solutions for Python, JavaScript, Java, C++, and C#. In all of them, the first thing the program does is iterate over every cell in the grid, checking if it is land (a 1 value). If it is, it will run a depth-first search to find the total connected land area, effectively finding an island. This whole process begins by creating a graph, and each node of the graph represents a distinct region of the grid.

When looking at all the solutions, it can be seen that they all follow the same approach but in different languages. The slight differences come from the way each language deals with certain operations, but fundamentally they all define the same steps.

In Python, JavaScript, and C#, the DFS uses recursive calls to check the other land cells (up, down, right, and left) are part of the same island, and every time it finds one, increases the count for that island.

In Java and C++, the DFS uses a loop that iterates over the four directions (up, down, right, and left) to achieve the same result as the recursive technique used in Python, JavaScript, and C#.

Finally, when DFS has completed for all islands, and we have a map that contains the size of each island, the algorithm loops over the grid once again. This time, if the cell is water (a 0 value), it looks at the four neighboring cells, and for each neighboring land found, adds their size to the current cell. If this total size is larger than the current max size, it updates it.

This way, it simulates the conversion of an ocean tile into a land tile (1) and connects the surrounding lands if any. The result is the maximum possible island area after making a single conversion.

Key Points:

1. DFS: Depth-First Search, in which we depart from every land square and visit every square connected to it. We can use DFS to help us find out the connected component (island) it is part of and the area of that island.

2. Map (or Dictionary): used to store the size of each distinct island.

3. Iterative second pass: For each sea square, count the area of connected land components. If we flipped this sea square to a land square, these lands could now all be joined.

4. Keep track of the global largest island area found so far.