Sponsored
Sponsored
This approach involves two main steps: firstly labeling all the islands in the grid using DFS, and secondly calculating the maximum possible island size by changing a '0' to a '1'.
1. Traverse the grid using DFS and label each island with a unique identifier. As you label the islands, keep track of the size of each island in a dictionary.
2. Iterate over each '0' cell in the grid, consider changing it to '1', and calculate the potential island size by inspecting neighboring cells.
3. Use a set to aggregate the neighboring island labels, and use the sizes from the dictionary to compute the total size.
This allows us to efficiently calculate the new island sizes by directly accessing individual island sizes using their labels.
Time Complexity: O(n^2), because each cell of the grid is visited at most twice, once for DFS and once for change evaluation.
Space Complexity: O(n^2) for storage of the labeled grid and area dictionary.
1def largestIsland(grid):
2 n = len(grid)
3
4 def dfs(x, y, index):
5 stack = [(x, y)]
6 grid[x][y] = index
7 area = 1
8 for x, y in stack:
9 for nx, ny in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
10 if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 1:
11 grid[nx][ny] = index
12 stack.append((nx, ny))
13 area += 1
14 return area
15
16 index_to_area = {0: 0}
17 index = 2
18 for i in range(n):
19 for j in range(n):
20 if grid[i][j] == 1:
21 index_to_area[index] = dfs(i, j, index)
22 index += 1
23
24 max_area = max(index_to_area.values())
25
26 for i in range(n):
27 for j in range(n):
28 if grid[i][j] == 0:
29 seen = set()
30 area = 1
31 for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
32 if 0 <= ni < n and 0 <= nj < n:
33 index = grid[ni][nj]
34 if index > 1:
35 seen.add(index)
36 area += sum(index_to_area[index] for index in seen)
37 max_area = max(max_area, area)
38
39 return max_areaThis code begins by defining a helper function dfs to traverse and mark connected islands. Each cell is associated with a unique island index, and the area of each island is stored in a dictionary.
The main loop iterates through all grid cells. For '1' cells, DFS is executed, labeling the island and calculating its area. '0' cells are evaluated by looking at their surrounding areas to calculate their possible contribution to an enlarged island size.