Leetcode 695. Max Area of Island (Python)

Related Topic

Depth-First-Search.

Description

Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

Sample I/O

Example 1

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]

Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.

Example 2

[[0,0,0,0,0,0,0,0]]

Given the above grid, return 0.

Note:

The length of each dimension in the given grid does not exceed 50.

Methodology

This question can be solved by Depth First Search and It is similar with question 200. Number of Islands.The difference is to find the largest island.

To find the largest island, we need to get area of each island. When we find a island we start to count the number of 1s in this island. we can move to four directions and there is no repeating path. We need to compare area of each island to the current largest island. Finally, we will have the area of the largest island

Code

def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        visited=set()
        max_size = 0
        row,col = len(grid),len(grid[0])
        directions=[(-1,0),(0,1),(1,0),(0,-1)]
        def dfs(x, y):
            area = 1
            for dx, dy in directions:
                nx,ny = x+dx, y+dy
                if 0<=nx<row and 0<=ny<col and (nx,ny) not in visited and grid[nx][ny]:
                    visited.add((nx,ny))
                    area+=dfs(nx,ny)
            return area
        
        for x in range(row):
            for y in range(col):
                if grid[x][y] and (x,y) not in visited:
                    visited.add((x,y))
                    max_size = max(dfs(x,y), max_size)
        return max_size

BigO

We iterate each cell will cost O(m*n) where m*n is the size of the 2D list. Each cell will also iterate four directions, so in total is O(m*n*4)