NeetCode #644LC-827HardAdvanced Graphs
← Back to All Problems#644 · #827 · Making A Large Island(最大人工岛)
📌 Problem Statement & Constraints
You are given an
n x n binary matrix grid. You may change at most one 0 to 1. Return the size of the largest island possible. Constraints: 1 <= n <= 500.💡 Core Algorithmic Approaches
- Label each existing island with a unique id and record its size.
- Then, for each
0cell, the island created by flipping it has size1 + sum of the distinct neighbouring islands' sizes. - The set of neighbouring labels is essential: the same island can touch the cell from several sides.
- If the grid is already all land, no flip is needed -- the answer is the whole grid.
💻 Benchmark Python3 Implementation
class Solution:
def largestIsland(self, grid: List[List[int]]) -> int:
n = len(grid)
label = [[0] * n for _ in range(n)]
sizes = {}
def dfs(r: int, c: int, lab: int) -> int:
if not (0 <= r < n and 0 <= c < n) or grid[r][c] != 1 or label[r][c]:
return 0
label[r][c] = lab
return (1 + dfs(r + 1, c, lab) + dfs(r - 1, c, lab)
+ dfs(r, c + 1, lab) + dfs(r, c - 1, lab))
lab = 2
for i in range(n):
for j in range(n):
if grid[i][j] == 1 and label[i][j] == 0:
sizes[lab] = dfs(i, j, lab)
lab += 1
best = max(sizes.values()) if sizes else 0 # no flip needed
for i in range(n):
for j in range(n):
if grid[i][j] == 0:
neighbours = set()
for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
nr, nc = i + dr, j + dc
if 0 <= nr < n and 0 <= nc < n and label[nr][nc]:
neighbours.add(label[nr][nc]) # dedupe!
best = max(best, 1 + sum(sizes[l] for l in neighbours))
return best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^2): one labelling pass plus one pass over the zeros.
💾 Space Complexity
O(n^2) for the label grid.
⚠️ Interview Pitfalls & Follow-ups
- Summing neighbour sizes without deduplication: the same island could be counted several times.
- Forgetting the no-flip case: an all-land grid's answer is
n^2, whichmax(sizes.values())gives. - Re-labelling per zero cell: the labels are computed once.
- Missing that flipping a zero also connects islands that were diagonal: only 4-directional neighbours matter.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.