Making A Large Island

LeetCode problem #827

Language Selection

Choose your preferred programming language

Showing: Python

Problem Statement

You are given an n x n binary grid grid where:

grid[r][c] = 1 represents land
grid[r][c] = 0 represents water

An island is a group of 1s connected 4-directionally (up, down, left, right).

You may change at most one 0 into a 1. Return the largest possible island area after this change.

If the grid already contains no 0, return the area of the whole grid.

Input / Output Format

Input: grid: int[][] (or equivalent) of size n x n with values 0 or 1
Output: int — maximum island area achievable by flipping at most one 0

Constraints

n == grid.length == grid[i].length
1 <= n <= 500
grid[i][j] is 0 or 1

Examples

Example 1

Input:

grid = [[1,0],
        [0,1]]

Output: 3
Explanation: Flip either 0 adjacent to both 1s (via the center connections). Flipping (0,1) connects (0,0) and (1,1) through adjacency? Actually with 4-direction only, flipping (0,1) connects to (0,0) and also to (1,1)? No—(0,1) is adjacent to (1,1), yes. So island size becomes 3.

Example 2

Input:

grid = [[1,1],
        [1,0]]

Output: 4
Explanation: Flip the only 0 to connect into the existing island of size 3, resulting in 4.

Example 3 (Edge Case: all land)

Input:

grid = [[1,1],
        [1,1]]

Output: 4
Explanation: No 0 to flip; answer is the whole grid.

Example 4 (Edge Case: all water)

Input:

grid = [[0,0],
        [0,0]]

Output: 1
Explanation: Flip any one cell to land; largest island size is 1.

Approach 1: Brute Force

Idea

For every 0 cell, temporarily flip it to 1, then compute the area of the largest island (via DFS/BFS), and take the maximum over all flips. Also consider the case where you flip nothing (grid already all 1s).

This is straightforward but expensive: doing a full traversal for each 0.

Algorithm

Count if there is any 0. If none, return n*n.
For each cell (r,c):
- If it is 0, flip to 1.
- Compute max island size in the whole grid using DFS/BFS with a visited array.
- Restore it to 0.
- Track the best result.
Return best.

Complexity

Let Z be number of zeros.
Each evaluation scans the grid: O(n^2), DFS also totals O(n^2).
Total: O(Z * n^2) worst-case O(n^4)
Space: O(n^2) for visited.

This will TLE for n=500, but it’s a useful baseline and interview stepping stone.

Brute Force Implementations

from collections import deque
from typing import List

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]:
            return 0
        n = len(grid)

        def max_island_area() -> int:
            visited = [[False] * n for _ in range(n)]
            best = 0

            for r in range(n):
                for c in range(n):
                    if grid[r][c] == 1 and not visited[r][c]:
                        q = deque([(r, c)])
                        visited[r][c] = True
                        area = 0
                        while q:
                            x, y = q.popleft()
                            area += 1
                            for dx, dy in ((1,0), (-1,0), (0,1), (0,-1)):
                                nx, ny = x + dx, y + dy
                                if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and grid[nx][ny] == 1:
                                    visited[nx][ny] = True
                                    q.append((nx, ny))
                        best = max(best, area)
            return best

        has_zero = any(grid[r][c] == 0 for r in range(n) for c in range(n))
        if not has_zero:
            return n * n

        ans = 1  # at least we can flip one zero to make island size 1
        for r in range(n):
            for c in range(n):
                if grid[r][c] == 0:
                    grid[r][c] = 1
                    ans = max(ans, max_island_area())
                    grid[r][c] = 0
        return ans

import java.util.*;

class Solution {
    public int largestIsland(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int n = grid.length;

        boolean hasZero = false;
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 0) { hasZero = true; break; }
            }
            if (hasZero) break;
        }
        if (!hasZero) return n * n;

        int ans = 1;
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 0) {
                    grid[r][c] = 1;
                    ans = Math.max(ans, maxIslandArea(grid));
                    grid[r][c] = 0;
                }
            }
        }
        return ans;
    }

    private int maxIslandArea(int[][] grid) {
        int n = grid.length;
        boolean[][] vis = new boolean[n][n];
        int best = 0;
        int[] dr = {1, -1, 0, 0};
        int[] dc = {0, 0, 1, -1};

        ArrayDeque<int[]> q = new ArrayDeque<>();
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 1 && !vis[r][c]) {
                    vis[r][c] = true;
                    q.add(new int[]{r, c});
                    int area = 0;

                    while (!q.isEmpty()) {
                        int[] cur = q.poll();
                        area++;
                        for (int k = 0; k < 4; k++) {
                            int nr = cur[0] + dr[k], nc = cur[1] + dc[k];
                            if (nr >= 0 && nr < n && nc >= 0 && nc < n && !vis[nr][nc] && grid[nr][nc] == 1) {
                                vis[nr][nc] = true;
                                q.add(new int[]{nr, nc});
                            }
                        }
                    }
                    best = Math.max(best, area);
                }
            }
        }
        return best;
    }
}

package main

type Solution struct{}

func (s Solution) LargestIsland(grid [][]int) int {
	if len(grid) == 0 || len(grid[0]) == 0 {
		return 0
	}
	n := len(grid)

	hasZero := false
	for r := 0; r < n && !hasZero; r++ {
		for c := 0; c < n; c++ {
			if grid[r][c] == 0 {
				hasZero = true
				break
			}
		}
	}
	if !hasZero {
		return n * n
	}

	maxIslandArea := func() int {
		vis := make([][]bool, n)
		for i := range vis {
			vis[i] = make([]bool, n)
		}
		best := 0
		dr := []int{1, -1, 0, 0}
		dc := []int{0, 0, 1, -1}

		type P struct{ r, c int }
		q := make([]P, 0)

		for r := 0; r < n; r++ {
			for c := 0; c < n; c++ {
				if grid[r][c] == 1 && !vis[r][c] {
					vis[r][c] = true
					q = q[:0]
					q = append(q, P{r, c})
					area := 0

					for head := 0; head < len(q); head++ {
						cur := q[head]
						area++
						for k := 0; k < 4; k++ {
							nr, nc := cur.r+dr[k], cur.c+dc[k]
							if nr >= 0 && nr < n && nc >= 0 && nc < n && !vis[nr][nc] && grid[nr][nc] == 1 {
								vis[nr][nc] = true
								q = append(q, P{nr, nc})
							}
						}
					}
					if area > best {
						best = area
					}
				}
			}
		}
		return best
	}

	ans := 1
	for r := 0; r < n; r++ {
		for c := 0; c < n; c++ {
			if grid[r][c] == 0 {
				grid[r][c] = 1
				if v := maxIslandArea(); v > ans {
					ans = v
				}
				grid[r][c] = 0
			}
		}
	}
	return ans
}

class Solution {
  largestIsland(grid) {
    if (!grid || grid.length === 0 || grid[0].length === 0) return 0;
    const n = grid.length;

    let hasZero = false;
    for (let r = 0; r < n && !hasZero; r++) {
      for (let c = 0; c < n; c++) if (grid[r][c] === 0) { hasZero = true; break; }
    }
    if (!hasZero) return n * n;

    const maxIslandArea = () => {
      const vis = Array.from({ length: n }, () => Array(n).fill(false));
      let best = 0;
      const dirs = [[1,0],[-1,0],[0,1],[0,-1]];

      for (let r = 0; r < n; r++) {
        for (let c = 0; c < n; c++) {
          if (grid[r][c] === 1 && !vis[r][c]) {
            let area = 0;
            const q = [[r, c]];
            vis[r][c] = true;

            for (let head = 0; head < q.length; head++) {
              const [x, y] = q[head];
              area++;
              for (const [dx, dy] of dirs) {
                const nx = x + dx, ny = y + dy;
                if (0 <= nx && nx < n && 0 <= ny && ny < n && !vis[nx][ny] && grid[nx][ny] === 1) {
                  vis[nx][ny] = true;
                  q.push([nx, ny]);
                }
              }
            }
            best = Math.max(best, area);
          }
        }
      }
      return best;
    };

    let ans = 1;
    for (let r = 0; r < n; r++) {
      for (let c = 0; c < n; c++) {
        if (grid[r][c] === 0) {
          grid[r][c] = 1;
          ans = Math.max(ans, maxIslandArea());
          grid[r][c] = 0;
        }
      }
    }
    return ans;
  }
}

using System;
using System.Collections.Generic;

public class Solution {
    public int LargestIsland(int[][] grid) {
        if (grid == null || grid.Length == 0 || grid[0] == null || grid[0].Length == 0) return 0;
        int n = grid.Length;

        bool hasZero = false;
        for (int r = 0; r < n && !hasZero; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 0) { hasZero = true; break; }
            }
        }
        if (!hasZero) return n * n;

        int MaxIslandArea() {
            bool[,] vis = new bool[n, n];
            int best = 0;
            int[] dr = { 1, -1, 0, 0 };
            int[] dc = { 0, 0, 1, -1 };

            var q = new Queue<(int r, int c)>();
            for (int r = 0; r < n; r++) {
                for (int c = 0; c < n; c++) {
                    if (grid[r][c] == 1 && !vis[r, c]) {
                        vis[r, c] = true;
                        q.Clear();
                        q.Enqueue((r, c));
                        int area = 0;

                        while (q.Count > 0) {
                            var (x, y) = q.Dequeue();
                            area++;
                            for (int k = 0; k < 4; k++) {
                                int nx = x + dr[k], ny = y + dc[k];
                                if (0 <= nx && nx < n && 0 <= ny && ny < n && !vis[nx, ny] && grid[nx][ny] == 1) {
                                    vis[nx, ny] = true;
                                    q.Enqueue((nx, ny));
                                }
                            }
                        }
                        best = Math.Max(best, area);
                    }
                }
            }
            return best;
        }

        int ans = 1;
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 0) {
                    grid[r][c] = 1;
                    ans = Math.Max(ans, MaxIslandArea());
                    grid[r][c] = 0;
                }
            }
        }
        return ans;
    }
}

Approach 2: Optimized Solution

Idea (Label islands + merge via one flip)

Instead of recomputing islands for each flip:

Label each existing island with a unique id (2,3,4,...) using DFS/BFS.
Store area[id] = size of that island.
For each 0 cell, look at its up to 4 neighbors, collect distinct island ids, and compute:
```
candidate = 1 + sum(area[id] for unique neighboring ids)
```
Take the maximum over all zeros; also consider existing max island if you flip nothing.

This is the standard optimal solution.

Complexity

Labeling pass: O(n^2)
For each cell, constant neighbor checks: O(n^2)
Total: O(n^2) time, O(n^2) space (grid relabel + area map + BFS queue)

Optimized Implementations

from collections import deque
from typing import List, Dict

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]:
            return 0
        n = len(grid)

        area: Dict[int, int] = {}
        island_id = 2  # start from 2 to distinguish from 0/1

        def bfs_mark(sr: int, sc: int, id_: int) -> int:
            q = deque([(sr, sc)])
            grid[sr][sc] = id_
            cnt = 0
            while q:
                r, c = q.popleft()
                cnt += 1
                for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 1:
                        grid[nr][nc] = id_
                        q.append((nr, nc))
            return cnt

        # 1) Label islands and compute their areas
        for r in range(n):
            for c in range(n):
                if grid[r][c] == 1:
                    area[island_id] = bfs_mark(r, c, island_id)
                    island_id += 1

        # If no zeros, whole grid is one island already (or multiple but fully land => still n*n)
        has_zero = any(grid[r][c] == 0 for r in range(n) for c in range(n))
        if not has_zero:
            return n * n

        ans = 1
        if area:
            ans = max(ans, max(area.values()))

        # 2) Try flipping each zero and merging adjacent islands
        for r in range(n):
            for c in range(n):
                if grid[r][c] != 0:
                    continue
                seen = set()
                total = 1
                for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < n:
                        id_ = grid[nr][nc]
                        if id_ >= 2 and id_ not in seen:
                            seen.add(id_)
                            total += area[id_]
                ans = max(ans, total)

        return ans

import java.util.*;

class Solution {
    public int largestIsland(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int n = grid.length;

        Map<Integer, Integer> area = new HashMap<>();
        int id = 2;
        int[] dr = {1, -1, 0, 0};
        int[] dc = {0, 0, 1, -1};

        // Label islands
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 1) {
                    int a = bfsMark(grid, r, c, id, dr, dc);
                    area.put(id, a);
                    id++;
                }
            }
        }

        boolean hasZero = false;
        for (int r = 0; r < n && !hasZero; r++) {
            for (int c = 0; c < n; c++) if (grid[r][c] == 0) { hasZero = true; break; }
        }
        if (!hasZero) return n * n;

        int ans = 1;
        for (int v : area.values()) ans = Math.max(ans, v);

        // Flip each zero
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] != 0) continue;

                int total = 1;
                // small fixed set of up to 4 ids
                int[] ids = new int[4];
                int sz = 0;

                for (int k = 0; k < 4; k++) {
                    int nr = r + dr[k], nc = c + dc[k];
                    if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
                    int nid = grid[nr][nc];
                    if (nid < 2) continue;

                    boolean dup = false;
                    for (int i = 0; i < sz; i++) if (ids[i] == nid) { dup = true; break; }
                    if (!dup) ids[sz++] = nid;
                }

                for (int i = 0; i < sz; i++) total += area.get(ids[i]);
                ans = Math.max(ans, total);
            }
        }
        return ans;
    }

    private int bfsMark(int[][] grid, int sr, int sc, int id, int[] dr, int[] dc) {
        int n = grid.length;
        ArrayDeque<int[]> q = new ArrayDeque<>();
        q.add(new int[]{sr, sc});
        grid[sr][sc] = id;
        int cnt = 0;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            cnt++;
            for (int k = 0; k < 4; k++) {
                int nr = cur[0] + dr[k], nc = cur[1] + dc[k];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 1) {
                    grid[nr][nc] = id;
                    q.add(new int[]{nr, nc});
                }
            }
        }
        return cnt;
    }
}

package main

type Solution struct{}

func (s Solution) LargestIsland(grid [][]int) int {
	if len(grid) == 0 || len(grid[0]) == 0 {
		return 0
	}
	n := len(grid)

	area := make(map[int]int)
	id := 2
	dr := [4]int{1, -1, 0, 0}
	dc := [4]int{0, 0, 1, -1}

	// BFS mark
	type P struct{ r, c int }
	bfsMark := func(sr, sc, id int) int {
		q := make([]P, 0, 16)
		q = append(q, P{sr, sc})
		grid[sr][sc] = id
		cnt := 0
		for head := 0; head < len(q); head++ {
			cur := q[head]
			cnt++
			for k := 0; k < 4; k++ {
				nr, nc := cur.r+dr[k], cur.c+dc[k]
				if nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 1 {
					grid[nr][nc] = id
					q = append(q, P{nr, nc})
				}
			}
		}
		return cnt
	}

	// Label islands
	for r := 0; r < n; r++ {
		for c := 0; c < n; c++ {
			if grid[r][c] == 1 {
				area[id] = bfsMark(r, c, id)
				id++
			}
		}
	}

	hasZero := false
	for r := 0; r < n && !hasZero; r++ {
		for c := 0; c < n; c++ {
			if grid[r][c] == 0 {
				hasZero = true
				break
			}
		}
	}
	if !hasZero {
		return n * n
	}

	ans := 1
	for _, v := range area {
		if v > ans {
			ans = v
		}
	}

	// Try flipping zeros
	for r := 0; r < n; r++ {
		for c := 0; c < n; c++ {
			if grid[r][c] != 0 {
				continue
			}
			total := 1
			seen := [4]int{0, 0, 0, 0}
			sz := 0

			for k := 0; k < 4; k++ {
				nr, nc := r+dr[k], c+dc[k]
				if nr < 0 || nr >= n || nc < 0 || nc >= n {
					continue
				}
				nid := grid[nr][nc]
				if nid < 2 {
					continue
				}
				dup := false
				for i := 0; i < sz; i++ {
					if seen[i] == nid {
						dup = true
						break
					}
				}
				if !dup {
					seen[sz] = nid
					sz++
				}
			}
			for i := 0; i < sz; i++ {
				total += area[seen[i]]
			}
			if total > ans {
				ans = total
			}
		}
	}
	return ans
}

class Solution {
  largestIsland(grid) {
    if (!grid || grid.length === 0 || grid[0].length === 0) return 0;
    const n = grid.length;

    const area = new Map();
    let id = 2;
    const dirs = [[1,0],[-1,0],[0,1],[0,-1]];

    const bfsMark = (sr, sc, idVal) => {
      const q = [[sr, sc]];
      grid[sr][sc] = idVal;
      let cnt = 0;

      for (let head = 0; head < q.length; head++) {
        const [r, c] = q[head];
        cnt++;
        for (const [dr, dc] of dirs) {
          const nr = r + dr, nc = c + dc;
          if (0 <= nr && nr < n && 0 <= nc && nc < n && grid[nr][nc] === 1) {
            grid[nr][nc] = idVal;
            q.push([nr, nc]);
          }
        }
      }
      return cnt;
    };

    // Label islands
    for (let r = 0; r < n; r++) {
      for (let c = 0; c < n; c++) {
        if (grid[r][c] === 1) {
          const a = bfsMark(r, c, id);
          area.set(id, a);
          id++;
        }
      }
    }

    let hasZero = false;
    for (let r = 0; r < n && !hasZero; r++) {
      for (let c = 0; c < n; c++) if (grid[r][c] === 0) { hasZero = true; break; }
    }
    if (!hasZero) return n * n;

    let ans = 1;
    for (const v of area.values()) ans = Math.max(ans, v);

    // Flip each zero
    for (let r = 0; r < n; r++) {
      for (let c = 0; c < n; c++) {
        if (grid[r][c] !== 0) continue;

        let total = 1;
        const seen = new Set();
        for (const [dr, dc] of dirs) {
          const nr = r + dr, nc = c + dc;
          if (0 <= nr && nr < n && 0 <= nc && nc < n) {
            const nid = grid[nr][nc];
            if (nid >= 2 && !seen.has(nid)) {
              seen.add(nid);
              total += area.get(nid);
            }
          }
        }
        ans = Math.max(ans, total);
      }
    }
    return ans;
  }
}

using System;
using System.Collections.Generic;

public class Solution {
    public int LargestIsland(int[][] grid) {
        if (grid == null || grid.Length == 0 || grid[0] == null || grid[0].Length == 0) return 0;
        int n = grid.Length;

        var area = new Dictionary<int, int>();
        int id = 2;
        int[] dr = { 1, -1, 0, 0 };
        int[] dc = { 0, 0, 1, -1 };

        int BfsMark(int sr, int sc, int idVal) {
            var q = new Queue<(int r, int c)>();
            q.Enqueue((sr, sc));
            grid[sr][sc] = idVal;
            int cnt = 0;

            while (q.Count > 0) {
                var (r, c) = q.Dequeue();
                cnt++;
                for (int k = 0; k < 4; k++) {
                    int nr = r + dr[k], nc = c + dc[k];
                    if (0 <= nr && nr < n && 0 <= nc && nc < n && grid[nr][nc] == 1) {
                        grid[nr][nc] = idVal;
                        q.Enqueue((nr, nc));
                    }
                }
            }
            return cnt;
        }

        // Label islands
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 1) {
                    int a = BfsMark(r, c, id);
                    area[id] = a;
                    id++;
                }
            }
        }

        bool hasZero = false;
        for (int r = 0; r < n && !hasZero; r++) {
            for (int c = 0; c < n; c++) if (grid[r][c] == 0) { hasZero = true; break; }
        }
        if (!hasZero) return n * n;

        int ans = 1;
        foreach (var v in area.Values) ans = Math.Max(ans, v);

        // Flip each zero
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] != 0) continue;

                int total = 1;
                var seen = new HashSet<int>();
                for (int k = 0; k < 4; k++) {
                    int nr = r + dr[k], nc = c + dc[k];
                    if (0 <= nr && nr < n && 0 <= nc && nc < n) {
                        int nid = grid[nr][nc];
                        if (nid >= 2 && seen.Add(nid)) {
                            total += area[nid];
                        }
                    }
                }
                ans = Math.Max(ans, total);
            }
        }

        return ans;
    }
}

Key Insights

Flipping a 0 can only merge the islands that touch it (up to 4).
If you precompute each island’s area and assign an id to each land cell, then each flip becomes a constant-time merge calculation.
Avoid double-counting by using a set (or small fixed array) of unique neighboring island ids.

Edge Cases

Grid is all 1s → answer n*n
Grid is all 0s → answer 1
Single cell grid: [[1]] → 1, [[0]] → 1
A 0 touches the same island from multiple sides (must deduplicate ids)
Multiple islands around a 0 (merge 2–4 islands)
Large n (must be O(n^2) to pass)

Test Cases

Python Test Code

def run_tests():
    sol = Solution()

    tests = [
        ([[1,0],[0,1]], 3),
        ([[1,1],[1,0]], 4),
        ([[1,1],[1,1]], 4),
        ([[0,0],[0,0]], 1),
        ([[0]], 1),
        ([[1]], 1),
        ([[1,0,1],
          [0,0,0],
          [1,0,1]], 3),
    ]

    for i, (grid, exp) in enumerate(tests):
        got = sol.largestIsland([row[:] for row in grid])
        assert got == exp, f"test {i} failed: got {got}, expected {exp}"
    print("All tests passed.")

# run_tests()

Java Test Code

import java.util.*;

public class Main {
    static void assertEq(int got, int exp, String name) {
        if (got != exp) throw new RuntimeException(name + " failed: got " + got + ", expected " + exp);
    }

    static int[][] copy(int[][] g) {
        int[][] c = new int[g.length][];
        for (int i = 0; i < g.length; i++) c[i] = Arrays.copyOf(g[i], g[i].length);
        return c;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        assertEq(sol.largestIsland(copy(new int[][]{{1,0},{0,1}})), 3, "ex1");
        assertEq(sol.largestIsland(copy(new int[][]{{1,1},{1,0}})), 4, "ex2");
        assertEq(sol.largestIsland(copy(new int[][]{{1,1},{1,1}})), 4, "all1");
        assertEq(sol.largestIsland(copy(new int[][]{{0,0},{0,0}})), 1, "all0");
        assertEq(sol.largestIsland(copy(new int[][]{{0}})), 1, "single0");
        assertEq(sol.largestIsland(copy(new int[][]{{1}})), 1, "single1");

        System.out.println("All tests passed.");
    }
}

Go Test Code

package main

import "fmt"

func copyGrid(g [][]int) [][]int {
	n := len(g)
	out := make([][]int, n)
	for i := 0; i < n; i++ {
		out[i] = make([]int, len(g[i]))
		copy(out[i], g[i])
	}
	return out
}

func assertEq(got, exp int, name string) {
	if got != exp {
		panic(fmt.Sprintf("%s failed: got %d expected %d", name, got, exp))
	}
}

func main() {
	sol := Solution{}

	assertEq(sol.LargestIsland(copyGrid([][]int{{1, 0}, {0, 1}})), 3, "ex1")
	assertEq(sol.LargestIsland(copyGrid([][]int{{1, 1}, {1, 0}})), 4, "ex2")
	assertEq(sol.LargestIsland(copyGrid([][]int{{1, 1}, {1, 1}})), 4, "all1")
	assertEq(sol.LargestIsland(copyGrid([][]int{{0, 0}, {0, 0}})), 1, "all0")
	assertEq(sol.LargestIsland(copyGrid([][]int{{0}})), 1, "single0")
	assertEq(sol.LargestIsland(copyGrid([][]int{{1}})), 1, "single1")

	fmt.Println("All tests passed.")
}

Common Mistakes

Double-counting the same island id when a 0 touches it from multiple sides.
Forgetting the all-ones case (should return n*n).
Using recursion DFS in languages with limited stack depth (may stack overflow for n=500); prefer iterative BFS/DFS.
Not copying the grid in tests (optimized solution mutates grid by relabeling).
Assuming diagonal connections count (they do not).

Interview Tips

Start with the brute force: “flip each zero and recompute” to show correctness thinking.
Then pivot: “we only need to know sizes of neighboring islands” → motivates labeling.
Explain dedup clearly: “a zero might touch the same island twice; use a set.”
Call out complexity improvement: from O(n^4) worst-case to O(n^2).
Mention implementation detail: iterative BFS to avoid recursion depth issues.