⚡Flashcard Drill➔
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

  1. Label each existing island with a unique id and record its size.
  2. Then, for each 0 cell, the island created by flipping it has size 1 + sum of the distinct neighbouring islands' sizes.
  3. The set of neighbouring labels is essential: the same island can touch the cell from several sides.
  4. 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, which max(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.
🎯 Drill This Card Now➔

🧩 Related Advanced Graphs Problems