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).

Pasted image 53.png

In this case, the answer clearly is:

Pasted image 54.png

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]].

Pasted image 55.png

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.

Pasted image 56.png

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))