Problem description:

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.

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:

For each 1 in the grid, we paint all connected 1 with the next available color (2, 3, and so on). We also remember the size of the island we just painted with that color.

Then, we analyze all 0 in the grid, and sum sizes of connected islands (based on the island color). Note that the same island can connect to 0 more than once. The example below demonstrates this idea (the answer is highlighted):

https://s3-lc-upload.s3.amazonaws.com/users/votrubac/image_1525310120.png

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
class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        def valid(i, j):
            return 0 if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) else grid[i][j]
        def paint(i, j, color):
            if valid(i, j) != 1: return 0
            grid[i][j] = color
            return 1 + paint(i+1, j, color) + paint(i-1, j, color) + paint(i, j+1, color) + paint(i, j-1, color)
        
        # paint all island to different color
        island = [0, 0] # color labeling starts from 2
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    island.append(paint(i, j, len(island)))
        res = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if not grid[i][j]:
                    visited = set()
                    visited.add(valid(i+1, j))
                    visited.add(valid(i-1, j))
                    visited.add(valid(i, j+1))
                    visited.add(valid(i, j-1))
                    res = max(res, 1 + sum(island[color] for color in visited))
        return len(grid)*len(grid[0]) if not res else res

time complexity: $O()$
space complexity: $O()$
reference:
related problem: