854 Making A Large Island
854 Making A Large Island
Making A Large Island 
You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1.
Return the size of the largest island in grid after applying this operation.
An island is a 4-directionally connected group of 1s.
Example 1:
1
2
3
4
5
**Input:** grid = [[1,0],[0,1]]
**Output:** 3
**Explanation:** Change one 0 to 1 and connect two 1s, then we get an island with area = 3.
Example 2:
1
2
3
4
**Input:** grid = [[1,1],[1,0]]
**Output:** 4
**Explanation: **Change the 0 to 1 and make the island bigger, only one island with area = 4.
Example 3:
1
2
3
4
5
**Input:** grid = [[1,1],[1,1]]
**Output:** 4
**Explanation:** Can't change any 0 to 1, only one island with area = 4.
Constraints:
1
2
3
4
n == grid.length
n == grid[i].length
1 <= n <= 500
grid[i][j] is either 0 or 1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
class Solution:
def largestIsland(self, grid: List[List[int]]) -> int:
island_sizes = {}
island_id = 2
# Step 1: Mark all islands and calculate their sizes
for current_row in range(len(grid)):
for current_column in range(len(grid[0])):
if grid[current_row][current_column] == 1:
island_sizes[island_id] = self.explore_island(
grid, island_id, current_row, current_column
)
island_id += 1
# If there are no islands, return 1
if not island_sizes:
return 1
# If the entire grid is one island, return its size or size +
if len(island_sizes) == 1:
island_id -= 1
return (
island_sizes[island_id]
if island_sizes[island_id] == len(grid) * len(grid[0])
else island_sizes[island_id] + 1
)
max_island_size = 1
# Step 2: Try converting every 0 to 1 and calculate the resulting island size
for current_row in range(len(grid)):
for current_column in range(len(grid[0])):
if grid[current_row][current_column] == 0:
current_island_size = 1
neighboring_islands = set()
# Check down
if (
current_row + 1 < len(grid)
and grid[current_row + 1][current_column] > 1
):
neighboring_islands.add(
grid[current_row + 1][current_column]
)
# Check up
if (
current_row - 1 >= 0
and grid[current_row - 1][current_column] > 1
):
neighboring_islands.add(
grid[current_row - 1][current_column]
)
# Check right
if (
current_column + 1 < len(grid[0])
and grid[current_row][current_column + 1] > 1
):
neighboring_islands.add(
grid[current_row][current_column + 1]
)
# Check left
if (
current_column - 1 >= 0
and grid[current_row][current_column - 1] > 1
):
neighboring_islands.add(
grid[current_row][current_column - 1]
)
# Sum the sizes of all unique neighboring islands
for island_id in neighboring_islands:
current_island_size += island_sizes[island_id]
max_island_size = max(max_island_size, current_island_size)
return max_island_size
def explore_island(
self,
grid: List[List[int]],
island_id: int,
current_row: int,
current_column: int,
) -> int:
if (
current_row < 0
or current_row >= len(grid)
or current_column < 0
or current_column >= len(grid[0])
or grid[current_row][current_column] != 1
):
return 0
grid[current_row][current_column] = island_id
return (
1
+ self.explore_island(
grid, island_id, current_row + 1, current_column
)
+ self.explore_island(
grid, island_id, current_row - 1, current_column
)
+ self.explore_island(
grid, island_id, current_row, current_column + 1
)
+ self.explore_island(
grid, island_id, current_row, current_column - 1
)
)
This post is licensed under CC BY 4.0 by the author.