Untitled

mail@pastecode.io avatar
unknown
python
2 months ago
1.2 kB
4
Indexable
Never
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        # traverse graph and at each island, dfs for area and track max

        # initialize vars
        seen = [row[:] for row in grid]
        stack = []
        rows = len(grid)
        cols = len(grid[0])
        max_area = 0
        dirs = [(0,1), (1,0), (0,-1), (-1,0)]

        def valid_coords(r, c):
            return 0 <= r < rows and 0 <= c < cols

        for r in range(rows):
            for c in range(cols):
                if seen[r][c] == 1:
                    # dfs and find area of island
                    area = 1
                    stack.append((r,c))
                    seen[r][c] = 0

                    while stack:
                        r, c = stack.pop()
                        
                        for dx, dy in dirs:
                            nr, nc = r + dy, r + dx

                            if valid_coords(nr, nc) and seen[nr][nc] == 1:
                                stack.append((nr, nc))
                                seen[nr][nc] = 0
                                area += 1

                    max_area = max(area, max_area)

        return max_area
Leave a Comment