max_area_of_island
1# @leet start 2class Solution: 3 def maxAreaOfIsland(self, grid: list[list[int]]) -> int: 4 """ 5 This problem asks to find the area of the largest island, 6 where an island is denoted by the number 1, and water is the number 0. 7 8 To find the max area, we iterate through the grid until we find a 1. 9 Then, the area of that island is 1 + the rest of the nodes dfsed. 10 11 We need to keep a visited set so we don't visit the same islands again 12 for each new island we see, make sure to update the max length with the 13 max length we've seen so far. 14 """ 15 m, n = len(grid), len(grid[0]) 16 max_size = 0 17 visited = set() 18 19 def inbounds(y, x): 20 return 0 <= y < m and 0 <= x < n 21 22 def dfs(y, x): 23 if not inbounds(y, x) or (y, x) in visited or grid[y][x] == 0: 24 return 0 25 visited.add((y, x)) 26 dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)] 27 return 1 + sum(dfs(dy + y, dx + x) for dy, dx in dirs) 28 29 for y in range(m): 30 for x in range(n): 31 if grid[y][x] == 1: 32 max_size = max(max_size, dfs(y, x)) 33 34 return max_size 35 36 37# @leet end 38 39 40def test(): 41 assert 2 + 2 == 4
class
Solution:
3class Solution: 4 def maxAreaOfIsland(self, grid: list[list[int]]) -> int: 5 """ 6 This problem asks to find the area of the largest island, 7 where an island is denoted by the number 1, and water is the number 0. 8 9 To find the max area, we iterate through the grid until we find a 1. 10 Then, the area of that island is 1 + the rest of the nodes dfsed. 11 12 We need to keep a visited set so we don't visit the same islands again 13 for each new island we see, make sure to update the max length with the 14 max length we've seen so far. 15 """ 16 m, n = len(grid), len(grid[0]) 17 max_size = 0 18 visited = set() 19 20 def inbounds(y, x): 21 return 0 <= y < m and 0 <= x < n 22 23 def dfs(y, x): 24 if not inbounds(y, x) or (y, x) in visited or grid[y][x] == 0: 25 return 0 26 visited.add((y, x)) 27 dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)] 28 return 1 + sum(dfs(dy + y, dx + x) for dy, dx in dirs) 29 30 for y in range(m): 31 for x in range(n): 32 if grid[y][x] == 1: 33 max_size = max(max_size, dfs(y, x)) 34 35 return max_size
def
maxAreaOfIsland(self, grid: list[list[int]]) -> int:
4 def maxAreaOfIsland(self, grid: list[list[int]]) -> int: 5 """ 6 This problem asks to find the area of the largest island, 7 where an island is denoted by the number 1, and water is the number 0. 8 9 To find the max area, we iterate through the grid until we find a 1. 10 Then, the area of that island is 1 + the rest of the nodes dfsed. 11 12 We need to keep a visited set so we don't visit the same islands again 13 for each new island we see, make sure to update the max length with the 14 max length we've seen so far. 15 """ 16 m, n = len(grid), len(grid[0]) 17 max_size = 0 18 visited = set() 19 20 def inbounds(y, x): 21 return 0 <= y < m and 0 <= x < n 22 23 def dfs(y, x): 24 if not inbounds(y, x) or (y, x) in visited or grid[y][x] == 0: 25 return 0 26 visited.add((y, x)) 27 dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)] 28 return 1 + sum(dfs(dy + y, dx + x) for dy, dx in dirs) 29 30 for y in range(m): 31 for x in range(n): 32 if grid[y][x] == 1: 33 max_size = max(max_size, dfs(y, x)) 34 35 return max_size
This problem asks to find the area of the largest island, where an island is denoted by the number 1, and water is the number 0.
To find the max area, we iterate through the grid until we find a 1. Then, the area of that island is 1 + the rest of the nodes dfsed.
We need to keep a visited set so we don't visit the same islands again for each new island we see, make sure to update the max length with the max length we've seen so far.
def
test():