Today’s problem

https://leetcode.com/problems/making-a-large-island/description/

Intuition

In this problem, we need to flip a 0 into a one to calculate the largest connected block. Now, if we can calculate the size of the connected block in the 4 directions of a 0 in the grid, then we just need to add them up and we are all set.

Approach

First we need to calculate the size of each connected block and give a label to each connected block so that we are not adding the same connected block twice.

Then we iterate all the 0, flip its result is the sum of the unique connected blocks around it in 4 directions.

Complexity

  • Time complexity: $O(N^2)$

  • Space complexity: $O(N^2)$

Code

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        islandCount = [0,0]
        dx = [0,0,1,-1]
        dy = [1,-1,0,0]
        n = len(grid)
        m = len(grid[0])
        
        def dfs(x, y, cnt):
            grid[x][y] = cnt
            islandCount[cnt] += 1
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or ny < 0 or nx >= n or ny >= m or grid[nx][ny] != 1:
                    continue
                
                dfs(nx, ny, cnt)

                
        cnt = 1
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    cnt += 1
                    islandCount.append(0)
                    dfs(i, j, cnt)
        
        ans = max(islandCount)

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 0:
                    tmp = 1
                    vis = set([])
                    for k in range(4):
                        nx = i + dx[k]
                        ny = j + dy[k] 
                        if nx < 0 or ny < 0 or nx >= n or ny >= m or grid[nx][ny] in vis:
                            continue
                        tmp += islandCount[grid[nx][ny]]
                        vis.add(grid[nx][ny])
                    
                    ans = max(ans, tmp)

        return ans