#827

Hard

auto_awesomeArray plus Depth-First Search

LeetCode Problem Workspace

Making A Large Island

Calculate the largest island size by converting at most one zero in a binary grid using array and DFS techniques efficiently.

array depth first search breadth first search union find matrix

Problem Statement

Given an n x n binary matrix grid, you may flip at most one 0 to a 1. An island is defined as a group of 1s connected 4-directionally. Your task is to determine the largest possible island area after performing at most one flip.

Return the maximum size of an island obtainable after flipping one zero. If the grid is already full of 1s, return the total number of cells. Constraints include 1 <= n <= 500 and each grid cell being 0 or 1.

Examples

Example 1

Input: grid = [[1,0],[0,1]]

Output: 3

Change one 0 to 1 and connect two 1s, then we get an island with area = 3.

Example 2

Input: grid = [[1,1],[1,0]]

Output: 4

Change the 0 to 1 and make the island bigger, only one island with area = 4.

Example 3

Input: grid = [[1,1],[1,1]]

Output: 4

Can't change any 0 to 1, only one island with area = 4.

Constraints

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

Solution Approach

Label islands with DFS

Perform a Depth-First Search to traverse the grid and assign a unique index to each island while recording its size. Store these sizes in a map for quick access when evaluating potential flips.

Evaluate each zero cell

For every zero in the grid, check its 4-directional neighbors and collect the indices of distinct adjacent islands. Summing their sizes plus one gives the potential new island size if that zero is flipped.

Compute maximum island

Iterate through all zeros and calculate the connected island sizes using the map from DFS labeling. Track the maximum encountered value and return it as the largest possible island area.

Complexity Analysis

Metric	Value
Time	O(n \times m)
Space	O(n \times m)

DFS labeling takes O(n m) time and O(n m) space to store visited states and island sizes. Evaluating each zero requires checking at most 4 neighbors, keeping the total time complexity within O(n*m).

What Interviewers Usually Probe

Checking DFS versus BFS trade-offs is important for large grids.
Remember to handle grids fully filled with 1s where no flips are needed.
Be ready to explain how using a map for island sizes avoids repeated recalculations.

Common Pitfalls or Variants

Common pitfalls

Counting the same island twice when multiple zeros share neighbors.
Not labeling islands correctly, leading to incorrect size computation.
Forgetting the edge case where no zeros exist, requiring total grid count.

Follow-up variants

Allow flipping multiple zeros and find maximum combined island size.
Use Union-Find instead of DFS to track connected components dynamically.
Compute largest island size when diagonal connections are also considered.

FAQ

What is the best approach pattern for Making A Large Island?

Using an array-based DFS pattern to label islands and map their sizes is the most direct method to determine the maximum area after one flip.

How do I handle a grid with no zeros?

If the grid has no zeros, the largest island is the entire grid, so simply return n*n without further computation.

Can BFS be used instead of DFS?

Yes, BFS can replace DFS for labeling islands, but DFS often provides simpler recursive implementation for tracking island sizes.

How should I avoid double-counting islands when flipping a zero?

Use a set to collect unique neighboring island indices before summing their sizes to prevent counting the same island multiple times.

What are the space and time considerations for large grids?

Both DFS and BFS require O(n m) space for visited cells and island sizes, and total time complexity remains O(n m), suitable for grids up to 500x500.

terminal

Solution

Solution 1: DFS

We can assign a unique identifier to each connected component, using an array $p$ to record the connected component each position belongs to, i.e., $p[i][j]$ represents the connected component number of $(i, j)$. Use an array $cnt$ to record the size of each connected component, i.e., $cnt[root]$ represents the size of the connected component $root$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        def dfs(i: int, j: int):
            p[i][j] = root
            cnt[root] += 1
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if 0 <= x < n and 0 <= y < n and grid[x][y] and p[x][y] == 0:
                    dfs(x, y)

        n = len(grid)
        cnt = Counter()
        p = [[0] * n for _ in range(n)]
        dirs = (-1, 0, 1, 0, -1)
        root = 0
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                if x and p[i][j] == 0:
                    root += 1
                    dfs(i, j)
        ans = max(cnt.values() or [0])
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                if x == 0:
                    s = set()
                    for a, b in pairwise(dirs):
                        x, y = i + a, j + b
                        if 0 <= x < n and 0 <= y < n:
                            s.add(p[x][y])
                    ans = max(ans, sum(cnt[root] for root in s) + 1)
        return ans

Continue Practicing

#778 swim in rising water #695 max area of island #959 regions cut by slashes