You are given an
m x n binary matrix
grid. 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.
The area of an island is the number of cells with a value
1 in the island.
Return the maximum area of an island in
grid. If there is no island, return
Input: grid = [[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]] Output: 6 Explanation: The answer is not 11, because the island must be connected 4-directionally.
Input: grid = [[0,0,0,0,0,0,0,0]] Output: 0
area+1and check the adjacent squares also.
max_areavariable by comparing with
areavariable should be reset to 0
class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: R,C=len(grid),len(grid) self.area=max_area=0 check=[[False]*C for _ in range(R)] def dfs(r,c): check[r][c]=True if grid[r][c]==1: self.area+=1 if c+1<C and not check[r][c+1]: dfs(r,c+1) if r+1<R and not check[r+1][c]: dfs(r+1,c) if c-1>=0 and not check[r][c-1]: dfs(r,c-1) if r-1>=0 and not check[r-1][c]: dfs(r-1,c) for i in range(R): for j in range(C): dfs(i,j) if max_area<self.area: max_area=self.area #print(f"max area",max_area) self.area=0 return max_area
Time Complexity: O(M*N)
M is the number of rows, and N is the number of colums.
We visit every square once.
the space used by
check to keep track of visited squares, and the space used by the call stack during our recursion.
globalvariable, the first solution is to use
classor nested function (pseudocode):