Making A Large Island

Problem

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.

Examples

Example 1:

1
2
3


Input: grid = [[1,0],[0,1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.

Example 2:

1
2
3


Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.

Example 3:

1
2
3


Input: grid = [[1,1],[1,1]]
Output: 4
Explanation: 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

Method 1 - Using DFS + Hashing

This problem will be similar to Number of Islands. Here is the approach:

Identify Islands: Traverse the grid to find and label all existing islands. Use DFS or BFS to calculate the size of each island. Store each island’s size in a dictionary.
Track Connectivity: Use a parent array to track the root of each cell in every island. Also, mark cells (0s) that, when flipped to 1, can connect two or more islands.
Simulate Flipping: For each 0, calculate the potential island size if that 0 is flipped to 1 by summing the sizes of all unique islands it would connect.
Calculate the Largest Island: Compare the size of the islands after each possible flip to find the maximum size.

Code

 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52


public class Solution {
    private int n;
    private final int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // Down, Up, Right, Left
    public int largestIsland(int[][] grid) {
        n = grid.length;
        int[] size = new int[n * n + 2];
        int id = 2; // Start from 2 because 1s are already used
        int maxSize = 0;

        // First pass: label every island with a unique id and calculate their size
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    size[id] = dfs(grid, i, j, id);
                    maxSize = Math.max(maxSize, size[id]);
                    id++;
                }
            }
        }

        // Second pass: check potential size by flipping each 0 to 1
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    Set<Integer> seenIds = new HashSet<>();
                    int potentialSize = 1; // The flipped cell itself
                    for (int[] dir : dirs) {
                        int newRow = i + dir[0];
                        int newCol = j + dir[1];
                        if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n && grid[newRow][newCol] != 0) {
                            int islandId = grid[newRow][newCol];
                            if (seenIds.add(islandId)) {
                                potentialSize += size[islandId];
                            }
                        }
                    }
                    maxSize = Math.max(maxSize, potentialSize);
                }
            }
        }
        return maxSize;
    }
    private int dfs(int[][] grid, int x, int y, int id) {
        if (x < 0 || x >= n || y < 0 || y >= n || grid[x][y] != 1) return 0;
        grid[x][y] = id;
        int size = 1;
        for (int[] dir : dirs) {
            size += dfs(grid, x + dir[0], y + dir[1], id);
        }
        return size;
    }
}

 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
32
33
34
35
36
37
38
39
40
41
42
43
44


class Solution:
    def __init__(self):
        self.n: int = 0
        self.dirs: List[List[int]] = [[1, 0], [-1, 0], [0, 1], [0, -1]] # Down, Up, Right, Left

    def largestIsland(self, grid: List[List[int]]) -> int:
        self.n = len(grid)
        size: List[int] = [0] * (self.n * self.n + 2)
        id: int = 2  # Start from 2 because 1s are already used
        maxSize: int = 0

        # First pass: label every island with a unique id and calculate their size
        for i in range(self.n):
            for j in range(self.n):
                if grid[i][j] == 1:
                    size[id] = self.dfs(grid, i, j, id)
                    maxSize = max(maxSize, size[id])
                    id += 1

        # Second pass: check potential size by flipping each 0 to 1
        for i in range(self.n):
            for j in range(self.n):
                if grid[i][j] == 0:
                    seenIds: Set[int] = set()
                    potentialSize: int = 1  # The flipped cell itself
                    for dir in self.dirs:
                        newRow, newCol = i + dir[0], j + dir[1]
                        if 0 <= newRow < self.n and 0 <= newCol < self.n and grid[newRow][newCol] != 0:
                            islandId = grid[newRow][newCol]
                            if islandId not in seenIds:
                                seenIds.add(islandId)
                                potentialSize += size[islandId]
                    maxSize = max(maxSize, potentialSize)

        return maxSize

    def dfs(self, grid: List[List[int]], x: int, y: int, id: int) -> int:
        if x < 0 or x >= self.n or y < 0 or y >= self.n or grid[x][y] != 1:
            return 0
        grid[x][y] = id
        sz: int = 1
        for dir in self.dirs:
            sz += self.dfs(grid, x + dir[0], y + dir[1], id)
        return sz

Complexity

⏰ Time complexity: O(n^2), since we potentially traverse the entire grid multiple times.
🧺 Space complexity: O(n^2), for storing island labels and sizes.

Problem#

Examples#

Solution#

Method 1 - Using DFS + Hashing#

Code#

Complexity#