LeetCode 827 - Making A Large Island

LeetCode Problem 827

Difficulty: 🔴 Hard
Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix

Solution

Problem Understanding

This problem asks us to find the largest possible island size in a binary grid after changing at most one 0 into 1.

The grid is an n x n matrix where:

• 1 represents land
• 0 represents water

An island is formed by land cells connected in the four cardinal directions:

• up
• down
• left
• right

Diagonal connections do not count.

The operation allowed is very important. We may flip at most one water cell into land. After performing this operation, we must compute the size of the largest connected island that can exist anywhere in the grid.

The output is a single integer representing that maximum island area.

The constraints are large:

• n can be as large as 500
• The grid may therefore contain up to 250,000 cells

This immediately tells us that expensive repeated traversals will not work. Any algorithm worse than roughly O(n²) will likely time out.

A naive approach might try flipping every 0 and recomputing island sizes from scratch each time, but that would require repeatedly scanning the grid. Since there may be O(n²) zero cells, and each scan may itself cost O(n²), the total complexity becomes O(n⁴), which is far too slow.

Several edge cases are important:

• The grid may already be entirely 1s. In this case, we cannot increase the island size, so the answer is simply n².
• The grid may contain all 0s. Flipping any one cell creates an island of size 1.
• A flipped 0 may connect multiple different islands together.
• Multiple neighboring cells may belong to the same island, so we must avoid double counting island sizes.
• Large connected components require an efficient traversal strategy.

The key challenge is efficiently determining how large an island becomes when a specific 0 cell is flipped.

Approaches

Brute Force Approach

The brute force solution considers every 0 cell independently.

For each water cell:

1. Temporarily change it to 1
2. Run a DFS or BFS to compute the size of the resulting island
3. Restore the cell back to 0
4. Track the maximum island size seen

This approach is correct because it explicitly evaluates every valid operation and computes the resulting island size exactly.

However, it is extremely inefficient.

There can be up to n² zero cells. For each one, we may perform a full DFS or BFS traversal across the grid, which itself costs O(n²).

This leads to:

• O(n²) candidate flips
• O(n²) traversal cost per flip

Total complexity becomes O(n⁴).

With n = 500, this is completely impractical.

Optimal Approach

The key observation is that island shapes do not change except at the flipped cell.

Instead of recomputing island sizes repeatedly, we can preprocess the grid once:

1. Identify every existing island
2. Assign each island a unique ID
3. Store the area of each island

After preprocessing, every land cell knows which island it belongs to.

Then, for each 0 cell:

• Look at its four neighbors
• Determine which unique islands touch it
• Sum their areas together
• Add 1 for the flipped cell itself

This works because flipping a 0 only affects the islands directly adjacent to it.

We avoid recomputation entirely by reusing precomputed island sizes.

The result is an efficient O(n²) solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n⁴)	O(n²)	Recompute island size for every possible flip
Optimal	O(n²)	O(n²)	Label islands once, then evaluate each zero cell efficiently

Algorithm Walkthrough

Step 1: Assign unique IDs to islands

We traverse the grid looking for unvisited land cells.

Whenever we find a 1 that has not yet been processed, we start a DFS or BFS to explore its entire connected component.

Instead of leaving cells as 1, we relabel them with a unique island ID such as 2, 3, 4, and so on.

We avoid using 0 and 1 because:

• 0 already means water
• 1 means unprocessed land

Using unique IDs lets us later identify which island a cell belongs to in constant time.

Step 2: Compute and store island sizes

During the DFS traversal, we count how many cells belong to the current island.

We store this in a hash map:

island_size[island_id] = area

For example:

{
    2: 5,
    3: 8,
    4: 2
}

This preprocessing allows instant lookup of any island's area later.

Step 3: Track the largest existing island

While labeling islands, we also track the maximum island area already present.

This handles the special case where the grid contains no 0s.

Step 4: Evaluate every zero cell

Now we iterate through every cell again.

For each 0 cell:

1. Create an empty set
2. Inspect its four neighbors
3. Add neighboring island IDs into the set
4. Sum the sizes of all unique neighboring islands
5. Add 1 for the flipped cell itself

The set is essential because the same island may touch the zero cell from multiple directions.

Without deduplication, we would incorrectly count the same island multiple times.

Step 5: Update the maximum answer

After computing the merged island size for a flipped cell, we update the global maximum.

At the end, this maximum is the answer.

Why it works

Every island is labeled exactly once, and its size is computed exactly once.

When evaluating a 0 cell, the only islands that can possibly become connected are its adjacent islands. Since we already know the exact size of each neighboring island, we can compute the merged area directly without any additional traversal.

Using a set guarantees that each island contributes its area only once, even if it touches the flipped cell from multiple sides.

Therefore, every possible valid flip is evaluated correctly, and the maximum achievable island size is returned.

Python Solution

from typing import List

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        n = len(grid)
        island_size = {}
        island_id = 2

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        def dfs(r: int, c: int, island_id: int) -> int:
            stack = [(r, c)]
            grid[r][c] = island_id
            area = 1

            while stack:
                row, col = stack.pop()

                for dr, dc in directions:
                    nr = row + dr
                    nc = col + dc

                    if (
                        0 <= nr < n
                        and 0 <= nc < n
                        and grid[nr][nc] == 1
                    ):
                        grid[nr][nc] = island_id
                        area += 1
                        stack.append((nr, nc))

            return area

        max_island = 0

        for r in range(n):
            for c in range(n):
                if grid[r][c] == 1:
                    area = dfs(r, c, island_id)
                    island_size[island_id] = area
                    max_island = max(max_island, area)
                    island_id += 1

        for r in range(n):
            for c in range(n):
                if grid[r][c] == 0:
                    neighboring_islands = set()
                    current_size = 1

                    for dr, dc in directions:
                        nr = r + dr
                        nc = c + dc

                        if 0 <= nr < n and 0 <= nc < n:
                            neighbor_id = grid[nr][nc]

                            if neighbor_id > 1:
                                neighboring_islands.add(neighbor_id)

                    for neighbor_id in neighboring_islands:
                        current_size += island_size[neighbor_id]

                    max_island = max(max_island, current_size)

        return max_island

The solution begins by scanning the grid to locate all existing islands.

Whenever an unprocessed land cell is found, the DFS function explores the full connected component and relabels all its cells using the current island ID. The DFS uses an explicit stack instead of recursion to avoid recursion depth issues on large grids.

Each island's area is stored in the island_size dictionary, allowing constant time lookup later.

After preprocessing, the algorithm scans the grid again looking for water cells. For each 0, it examines the four neighboring positions and collects all distinct neighboring island IDs into a set.

The sizes of those islands are summed together, and 1 is added for the flipped cell itself.

The algorithm continuously updates the maximum island size found and returns the final answer.

Go Solution

package main

func largestIsland(grid [][]int) int {
	n := len(grid)

	directions := [][]int{
		{1, 0},
		{-1, 0},
		{0, 1},
		{0, -1},
	}

	islandSize := make(map[int]int)
	islandID := 2

	var dfs func(int, int, int) int

	dfs = func(r int, c int, id int) int {
		stack := [][]int{{r, c}}
		grid[r][c] = id
		area := 1

		for len(stack) > 0 {
			last := len(stack) - 1
			cell := stack[last]
			stack = stack[:last]

			row := cell[0]
			col := cell[1]

			for _, d := range directions {
				nr := row + d[0]
				nc := col + d[1]

				if nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 1 {
					grid[nr][nc] = id
					area++
					stack = append(stack, []int{nr, nc})
				}
			}
		}

		return area
	}

	maxIsland := 0

	for r := 0; r < n; r++ {
		for c := 0; c < n; c++ {
			if grid[r][c] == 1 {
				area := dfs(r, c, islandID)
				islandSize[islandID] = area

				if area > maxIsland {
					maxIsland = area
				}

				islandID++
			}
		}
	}

	for r := 0; r < n; r++ {
		for c := 0; c < n; c++ {
			if grid[r][c] == 0 {
				seen := make(map[int]bool)
				currentSize := 1

				for _, d := range directions {
					nr := r + d[0]
					nc := c + d[1]

					if nr >= 0 && nr < n && nc >= 0 && nc < n {
						neighborID := grid[nr][nc]

						if neighborID > 1 && !seen[neighborID] {
							seen[neighborID] = true
							currentSize += islandSize[neighborID]
						}
					}
				}

				if currentSize > maxIsland {
					maxIsland = currentSize
				}
			}
		}
	}

	return maxIsland
}

The Go implementation closely mirrors the Python solution.

Instead of Python sets, Go uses a map[int]bool to track which neighboring islands have already been counted.

The DFS uses an explicit slice-based stack to avoid recursive depth limitations.

Go slices are dynamically resized during stack operations, making them convenient for iterative DFS traversal.

Since the maximum possible island size is at most 250,000, standard Go integers are completely sufficient and overflow is not a concern.

Worked Examples

Example 1

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

Step 1: Label islands

We discover two separate islands.

Position	Assigned ID	Area
(0,0)	2	1
(1,1)	3	1

Grid becomes:

[
  [2,0],
  [0,3]
]

Island map:

{
  2: 1,
  3: 1
}

Step 2: Evaluate zero cells

Flip cell (0,1)

Neighbors:

• left → island 2
• down → island 3

Combined size:

1 + 1 + 1 = 3

Flip cell (1,0)

Neighbors:

• up → island 2
• right → island 3

Combined size:

1 + 1 + 1 = 3

Maximum answer:

3

Example 2

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

Step 1: Label islands

Entire land mass is connected.

Island ID	Area
2	3

Grid becomes:

[
  [2,2],
  [2,0]
]

Step 2: Evaluate zero cell

Cell (1,1) touches island 2.

Combined size:

1 + 3 = 4

Answer:

4

Example 3

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

Step 1: Label islands

Single island:

Island ID	Area
2	4

There are no zero cells to flip.

Maximum island already equals:

4

Answer:

4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Each cell is processed a constant number of times
Space	O(n²)	Island labels, stack, and hash map storage

The DFS traversal visits each land cell exactly once during preprocessing. Later, each grid cell is examined again when evaluating possible flips.

Because every operation on a cell takes constant time, the total runtime is proportional to the number of cells in the grid.

The auxiliary space comes from:

• storing island sizes
• DFS stack usage
• relabeling information already embedded in the grid

In the worst case, these structures may collectively require O(n²) space.

Test Cases

from typing import List

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        n = len(grid)
        island_size = {}
        island_id = 2

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        def dfs(r: int, c: int, island_id: int) -> int:
            stack = [(r, c)]
            grid[r][c] = island_id
            area = 1

            while stack:
                row, col = stack.pop()

                for dr, dc in directions:
                    nr = row + dr
                    nc = col + dc

                    if (
                        0 <= nr < n
                        and 0 <= nc < n
                        and grid[nr][nc] == 1
                    ):
                        grid[nr][nc] = island_id
                        area += 1
                        stack.append((nr, nc))

            return area

        max_island = 0

        for r in range(n):
            for c in range(n):
                if grid[r][c] == 1:
                    area = dfs(r, c, island_id)
                    island_size[island_id] = area
                    max_island = max(max_island, area)
                    island_id += 1

        for r in range(n):
            for c in range(n):
                if grid[r][c] == 0:
                    neighboring_islands = set()
                    current_size = 1

                    for dr, dc in directions:
                        nr = r + dr
                        nc = c + dc

                        if 0 <= nr < n and 0 <= nc < n:
                            neighbor_id = grid[nr][nc]

                            if neighbor_id > 1:
                                neighboring_islands.add(neighbor_id)

                    for neighbor_id in neighboring_islands:
                        current_size += island_size[neighbor_id]

                    max_island = max(max_island, current_size)

        return max_island

sol = Solution()

assert sol.largestIsland([[1,0],[0,1]]) == 3  # connects two islands
assert sol.largestIsland([[1,1],[1,0]]) == 4  # expand existing island
assert sol.largestIsland([[1,1],[1,1]]) == 4  # already full land
assert sol.largestIsland([[0,0],[0,0]]) == 1  # all water
assert sol.largestIsland([[1]]) == 1  # single land cell
assert sol.largestIsland([[0]]) == 1  # single water cell
assert sol.largestIsland([[1,0,1],[0,0,0],[1,0,1]]) == 3  # disconnected corners
assert sol.largestIsland([[1,1,0],[1,0,1],[0,1,1]]) == 7  # merge multiple islands
assert sol.largestIsland([[1,1,1],[1,0,1],[1,1,1]]) == 9  # central flip creates full grid
assert sol.largestIsland([[0,1,0],[1,0,1],[0,1,0]]) == 5  # connect four directions

Test	Why
[[1,0],[0,1]]	Verifies merging two islands
[[1,1],[1,0]]	Verifies expanding a single island
[[1,1],[1,1]]	Ensures all-land case works
[[0,0],[0,0]]	Ensures all-water case works
[[1]]	Smallest possible land grid
[[0]]	Smallest possible water grid
Disconnected corner islands	Ensures no accidental diagonal connection
Multi-island merge case	Verifies combining several neighboring islands
Central flip in dense grid	Tests maximum possible merge
Four-direction merge	Ensures deduplication and neighbor handling

Edge Cases

Grid contains only land

If the grid is already entirely filled with 1s, there is no valid 0 to flip. A buggy implementation might incorrectly return 0 or fail to handle this situation.

This implementation handles it correctly because the preprocessing phase computes the size of existing islands and stores the maximum island size immediately. Even if the second pass never finds a 0, the correct maximum already exists.

Grid contains only water

If every cell is 0, then no existing islands exist.

A naive implementation may fail because there are no island IDs or island sizes to reference.

This solution handles the case naturally. Every zero cell evaluates to:

1

because flipping that single cell creates a one-cell island.

A zero touches the same island multiple times

Consider:

[
  [1,1],
  [1,0]
]

The bottom-right zero touches the same island from both the top and left sides.

Without deduplication, the island size would incorrectly be counted twice.

This implementation uses a set of neighboring island IDs before summing areas, guaranteeing each island contributes only once.

Large connected components

With n = 500, recursive DFS may exceed recursion limits in some languages.

This implementation uses iterative DFS with an explicit stack, avoiding stack overflow issues while still exploring the island efficiently.