# making a large island

🏠

This is a beautiful algorithm, and the official solution to leetcode 827.

In a 2D grid of 0s and 1s, we change at most one 0 to a 1.
After, what is the size of the largest island? (An island is a 4-directionally connected group of 1s).

In this case, the answer clearly is:

You may want to think of a solution before reading on. Like most graph problems, the solution is pretty simple and straight-forward.

## Label and measure islands

The first step is to label the islands, this can be done quite similarly to [[island count]], i.e by using either a [[dfs]] or a [[bfs]].

While labeling them, it's also trivial to measure their sizes, {2:8, 3:2, 4:1}.

## Check neighbours of 0s

Finally, we want to iterate over each 0, and for each of its neighbours and sum up their areas, plus one.

We simply need to track the maximum of that number, and this is our answer.

Result: 11.

## Implementation

### Neighbours

Fetching neighbours is something we'll do a lot of, so it deserves its own function.

1 def neighbors(r, c):
2   for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
3       if 0 <= nr < N and 0 <= nc < N:
4           yield nr, nc


## DFS

The DFS labels and measures the islands.

1 def dfs(r, c, index):
2   ans = 1
3   grid[r][c] = index
4   for nr, nc in neighbors(r, c):
5       if grid[nr][nc] == 1:
6           ans += dfs(nr, nc, index)
7   return ans


We perform the DFS over the entire grid, while storing our area measurements for later use.

1 area = {}
2 index = 2
3 for r in range(N):
4   for c in range(N):
5       if grid[r][c] == 1:
6           area[index] = dfs(r, c, index)
7           index += 1


Finally we iterate over the 0s, and sum up the areas of their neighbours:

1 ans = max(area.values() or [0])
2 for r in range(N):
3   for c in range(N):
4       if grid[r][c] == 0:
5           seen = {
6               grid[nr][nc] for nr, nc in neighbors(r, c) if grid[nr][nc] > 1
7           }
8           ans = max(ans, 1 + sum(area[i] for i in seen))
9 return ans


## Putting it all together

 1 class Solution(object):
2     def largestIsland(self, grid):
3         N = len(grid)
4
5         def neighbors(r, c):
6             for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
7                 if 0 <= nr < N and 0 <= nc < N:
8                     yield nr, nc
9
10         def dfs(r, c, index):
11             ans = 1
12             grid[r][c] = index
13             for nr, nc in neighbors(r, c):
14                 if grid[nr][nc] == 1:
15                     ans += dfs(nr, nc, index)
16             return ans
17
18         area = {}
19         index = 2
20         for r in range(N):
21             for c in range(N):
22                 if grid[r][c] == 1:
23                     area[index] = dfs(r, c, index)
24                     index += 1
25
26         ans = max(area.values() or [0])
27         for r in range(N):
28             for c in range(N):
29                 if grid[r][c] == 0:
30                     seen = {
31                         grid[nr][nc] for nr, nc in neighbors(r, c) if grid[nr][nc] > 1
32                     }
33                     ans = max(ans, 1 + sum(area[i] for i in seen))
34         return ans
35
36
37 isl = [
38     [0, 1, 1, 1, 0],
39     [0, 1, 1, 1, 0],
40     [0, 1, 1, 0, 0],
41     [0, 0, 0, 0, 0],
42     [1, 1, 0, 1, 0],
43 ]
44
45 print(Solution().largestIsland(isl))