Advertisement
smj007

Untitled

Aug 15th, 2023 (edited)
1,139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.49 KB | None | 0 0
  1. O(MxN) time, O(1) space
  2. class Solution:
  3.     def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
  4.  
  5.  
  6.         def dfs(r, c):
  7.  
  8.             if r<0 or r>=rows or c<0 or c>=cols or grid[r][c] == 0:
  9.                 return 0
  10.  
  11.             # mark the current node as visited
  12.             grid[r][c] = 0
  13.  
  14.             return 1 + dfs(r+1, c) + dfs(r-1, c) + dfs(r, c+1) + dfs(r, c-1)
  15.  
  16.         rows = len(grid)
  17.         cols = len(grid[0])
  18.         max_area = 0
  19.  
  20.         for r in range(rows):
  21.             for c in range(cols):
  22.                 if grid[r][c] == 1:
  23.                     max_area = max(max_area, dfs(r, c))
  24.  
  25.         return max_area
  26.  
  27. O(MxN) time, O(MxN) space
  28. class Solution:
  29.     def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
  30.        
  31.         def dfs(r, c):
  32.             if (r<0 or r>=n or c<0 or c>=m) or (r, c) in visited or grid[r][c] == 0:
  33.                 return 0
  34.  
  35.             # add to visited
  36.             visited.add((r, c))
  37.  
  38.             # focus on the recursive formulat, I think you completely messed up the recursive formula
  39.             return 1+ dfs(r+1, c) + dfs(r-1, c) + dfs(r, c+1) + dfs(r, c-1)
  40.  
  41.         visited = set()
  42.         n = len(grid)
  43.         m = len(grid[0])
  44.         maxArea = 0
  45.  
  46.         for r in range(n):
  47.             for c in range(m):
  48.                 # no need to have checks here as you were having. have checks in the base case only
  49.                 area = dfs(r, c)
  50.                 maxArea = max(area, maxArea)
  51.  
  52.         return maxAreaa
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement