Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- O(MxN) time, O(1) space
- class Solution:
- def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
- def dfs(r, c):
- if r<0 or r>=rows or c<0 or c>=cols or grid[r][c] == 0:
- return 0
- # mark the current node as visited
- grid[r][c] = 0
- return 1 + dfs(r+1, c) + dfs(r-1, c) + dfs(r, c+1) + dfs(r, c-1)
- rows = len(grid)
- cols = len(grid[0])
- max_area = 0
- for r in range(rows):
- for c in range(cols):
- if grid[r][c] == 1:
- max_area = max(max_area, dfs(r, c))
- return max_area
- O(MxN) time, O(MxN) space
- class Solution:
- def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
- def dfs(r, c):
- if (r<0 or r>=n or c<0 or c>=m) or (r, c) in visited or grid[r][c] == 0:
- return 0
- # add to visited
- visited.add((r, c))
- # focus on the recursive formulat, I think you completely messed up the recursive formula
- return 1+ dfs(r+1, c) + dfs(r-1, c) + dfs(r, c+1) + dfs(r, c-1)
- visited = set()
- n = len(grid)
- m = len(grid[0])
- maxArea = 0
- for r in range(n):
- for c in range(m):
- # no need to have checks here as you were having. have checks in the base case only
- area = dfs(r, c)
- maxArea = max(area, maxArea)
- return maxAreaa
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement