Making a Large Island — Color Map and Merge (LC 827)

Problem Statement#

LeetCode 827 — Making a Large Island (Hard)

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.

Constraints:

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

Example:

Input: grid = [[1,0],[0,1]]
Output: 3
Explanation: Change one 0 to 1 and connect the two 1 islands; the merged island has area 3.
 
Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the only 0 to 1; all four cells form a single island.
 
Input: grid = [[1,1],[1,1]]
Output: 4
Explanation: No 0 to flip; the existing island has area 4.

Why This Problem Matters#

Making a Large Island is the canonical "color and merge" graph problem and a famously sneaky Google interview question. The naive approach — for each 0, flip it, run DFS, track max — is O(n^4) and times out on a 500x500 grid. Solving it in O(n^2) requires a clever two-phase strategy: assign each existing island a unique ID and pre-compute its area, then for each 0 candidate, sum the areas of distinct neighboring islands plus one.

The pattern teaches you how to decouple structure from queries — a critical skill that shows up in graph compression, heavy-light decomposition, and offline query problems. Anyone who has interviewed at Google or Stripe knows this problem because it appears in the prep packets and has been used in onsite loops for years.

The Core Insight#

Two ideas work together:

1. Color phase. Run DFS once across the grid. Give every distinct island a unique integer ID (start from 2 since the grid uses 0/1). Compute and store each island's area in a hash map keyed by ID.
2. Query phase. For every 0 cell, look at its 4 neighbors. Collect the distinct island IDs (a set), sum their areas, add 1 for the flipped cell, and update the running maximum.

The deduplication via a set is critical: a 0 cell may have two neighbors that belong to the same island (think of a U-shape), and we must not double-count.

The edge case: if there are no 0s at all, the entire grid is one island; return n times n.

Why O(n^2)? The color phase visits every cell once. The query phase iterates over every 0 and inspects up to 4 neighbors per cell — constant work per cell. Total: O(n^2).

Visual Dry Run#

Grid:

1 1 0
1 0 1
0 1 1

Color phase. Two existing islands:

• Island ID 2: cells {(0,0), (0,1), (1,0)}, area = 3.
• Island ID 3: cells {(1,2), (2,1), (2,2)}, area = 3.

Colored grid:

2 2 0
2 0 3
0 3 3

area = {2: 3, 3: 3}.

Query phase.

Answer: 7.

Solution (Optimal)#

Python#

class Solution:
    def largestIsland(self, grid: list[list[int]]) -> int:
        N = len(grid)
        area = {}                                # island_id -> area
        next_id = 2                              # ids start at 2; 0/1 reserved
 
        def dfs(r: int, c: int, idx: int) -> int:
            if not (0 <= r < N and 0 <= c < N) or grid[r][c] != 1:
                return 0
            grid[r][c] = idx                     # paint cell with island ID
            return (1
                    + dfs(r + 1, c, idx)
                    + dfs(r - 1, c, idx)
                    + dfs(r, c + 1, idx)
                    + dfs(r, c - 1, idx))
 
        # 1) color every island and store its area
        for r in range(N):
            for c in range(N):
                if grid[r][c] == 1:
                    area[next_id] = dfs(r, c, next_id)
                    next_id += 1
 
        # special case: grid is entirely 1s
        if not area:
            return 0
        if all(v == N * N for v in area.values()):
            return N * N
 
        best = max(area.values())                # best without any flip
 
        # 2) try flipping each 0
        for r in range(N):
            for c in range(N):
                if grid[r][c] == 0:
                    seen_ids = set()
                    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:
                            seen_ids.add(grid[nr][nc])
                    merged = 1 + sum(area[i] for i in seen_ids)
                    best = max(best, merged)
        return best

JavaScript#

/**
 * @param {number[][]} grid
 * @return {number}
 */
var largestIsland = function(grid) {
    const N = grid.length;
    const area = new Map();                      // id -> area
    let nextId = 2;
 
    function dfs(r, c, id) {
        if (r < 0 || r >= N || c < 0 || c >= N || grid[r][c] !== 1) return 0;
        grid[r][c] = id;                         // paint with island ID
        return 1
             + dfs(r + 1, c, id)
             + dfs(r - 1, c, id)
             + dfs(r, c + 1, id)
             + dfs(r, c - 1, id);
    }
 
    // 1) color phase
    for (let r = 0; r < N; r++) {
        for (let c = 0; c < N; c++) {
            if (grid[r][c] === 1) {
                area.set(nextId, dfs(r, c, nextId));
                nextId++;
            }
        }
    }
 
    if (area.size === 0) return 1;               // grid is all 0s, flipping one gives 1
    let best = Math.max(...area.values());
 
    const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
 
    // 2) query phase: try each 0
    for (let r = 0; r < N; r++) {
        for (let c = 0; c < N; c++) {
            if (grid[r][c] !== 0) continue;
            const ids = new Set();
            for (const [dr, dc] of dirs) {
                const nr = r + dr, nc = c + dc;
                if (nr >= 0 && nr < N && nc >= 0 && nc < N && grid[nr][nc] > 1) {
                    ids.add(grid[nr][nc]);
                }
            }
            let merged = 1;
            for (const id of ids) merged += area.get(id);
            best = Math.max(best, merged);
        }
    }
    return best;
};

Time Complexity: O(n^2) — both phases are linear in cells. Space Complexity: O(n^2) for the recursion stack and the area map.

Common Mistakes#

1. Counting duplicate neighbors. Using a list instead of a set causes the same island to be added multiple times — produces wildly inflated answers on U-shaped layouts.
2. Starting island IDs at 1. The grid already uses 1 for unvisited land. Use 2 and up to avoid collisions during the query phase.
3. Forgetting the all-zero or all-one edge cases. If grid is all 0s, the answer is 1 (flip one zero). If grid is all 1s, the answer is n times n and there is no zero to flip.
4. Re-running DFS in the query phase. This is the brute-force trap that turns the algorithm into O(n^4).
5. Not initializing best to the largest existing island. If no flip improves the answer, you still need to return the original maximum island size.

Interview Tips#

• Walk through the two phases distinctly. "Phase 1: color and measure. Phase 2: query each candidate flip." This signals structured thinking.
• Emphasize the deduplication. Show the U-shape example explicitly — it is the bug interviewers love to plant.
• Mention Union-Find. A DSU-based solution also works: union neighboring 1 cells, store size by root, then for each 0 sum the sizes of distinct roots. Same complexity, alternate flavor.
• Start ID numbering at 2. Tell the interviewer why so they know you considered the collision.

Follow-up Questions#

1. What if you can flip up to k zeros? Becomes substantially harder; brute force k! combinations is exponential. Heuristic search or DP over connected regions is required.
2. What if the grid is 3D? Same algorithm; expand to 6 directions.
3. What if islands are 8-connected? Just expand the direction set in DFS and the query phase.
4. Streaming version? Use Union-Find to merge as cells are added; always cheap.

Key Takeaways#

• Making a Large Island is solved with two passes: color and query — never re-DFS during the query phase.
• Assign island IDs starting at 2 to avoid collisions with the input grid values.
• Use a set when summing neighbor island areas; duplicates wreck the answer.
• Initialize best to the largest pre-existing island so the no-flip case is covered.
• Watch the all-zero and all-one edge cases explicitly.
• Union-Find is an equivalent alternate solution and a good follow-up to mention in interviews.