Problem statement

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

Solution

What we need to do is to find all islands first (very similar to 0694 Number of Distinct Islands), we can do it in place: for each island we rewrite it with its number (we start enumerate from 2, because 0 and 1 already reserved), also we evaluate size of each island in island Counter. Then we need to traverse our grid once again and for each empty cell check four neighbors: and create set off all unique islands (it can happen that for example left neighbor and upper neighbor are the same island). Then we evaluate sum of sizes of all neighbours and choose the biggest one.

Complexity

Time complexity is O(n*m), because we traverse our graph twice: one with dfs and another when we were looking for empty cells. Space complxity is potentially O(n*m) as well.

Code

class Solution:
    def largestIsland(self, grid):
        m, n = len(grid), len(grid[0])
        neib_list = [[1,0],[-1,0],[0,-1],[0,1]]
        islands, count, ans = Counter(), 2, 0
        
        def dfs(t, i, j):
            if not 0 <= i < m or not 0 <= j < n or grid[i][j] != 1: return
            islands[t] += 1
            grid[i][j] = t
            for x, y in neib_list: dfs(t, x+i, y+j)
                
        for x, y in product(range(m), range(n)):
            if grid[x][y] == 1:
                dfs(count, x, y)
                count += 1
                
        for x, y in product(range(m), range(n)):
            if grid[x][y] != 0: continue
            neibs = set()
            for dx, dy in neib_list:
                if 0 <= x + dx < m and 0 <= y + dy < n and grid[x+dx][y+dy] != 0:
                    neibs.add(grid[x+dx][y+dy])
            ans = max(ans, sum(islands[i] for i in neibs) + 1)
            
        return ans if ans != 0 else m*n