Archived
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 [[number of islands]], i.e by using either a [[depth first search]] 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.
1def 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.
1def 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.
1area = {}
2index = 2
3for 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:
1ans = max(area.values() or [0])
2for 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))
9return ans
Putting it all together
1class 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
37isl = [
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
45print(Solution().largestIsland(isl))