Problem statement

https://leetcode.com/problems/max-area-of-island/

Solution

When you see problem about islands, you most probably should use dfs or bfs. It is possible to use any of them, for me dfs is a bit simpler to code. We start dfs from every not visited yet point and I direclty change grid cell to # symbol (we can change it back in the end if needed). For every island we count number of nodes inside this island and keep it in Counter. In the end we traverse all islands and choose the biggest one.

Complexity

Time complexity is O(mn), because we visit each edge in our graph only once. Space complexity can also be potentially O(mn) here.

Code

class Solution:
    def maxAreaOfIsland(self, grid):
        m, n = len(grid), len(grid[0])
        neibs = [[1,0],[-1,0],[0,-1],[0,1]]
        islands, count = Counter(), 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] = '#'
            for x, y in neibs: dfs(t, x+i, y+j)
        
        for i, j in product(range(m), range(n)):
            if grid[i][j] == 1:
                dfs(count, i, j)
                count += 1
                
        return max(list(islands.values()) + [0])