Leetcode 695 -- Max Area of Island.py

# Leetcode 695: Max Area of Island
# https://leetcode.com/problems/max-area-of-island/

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        area = 0 # keep track of largest area so far
        m, n = len(grid), len(grid[0])
        seen = set() # list of nodes we have visited before
        directions = [(0,1),(1,0),(-1,0),(0,-1)] # how we are allowed to move

        # check if step is within boundary
        def valid (row, col) -> bool:
            return 0 <= row < m and 0 <= col < n and grid[row][col] == 1

        def dfs (row, col) -> int:
            size = 1
            seen.add((row, col))
            for dx, dy in directions:
                next_row, next_col = dx + row, dy + col
                if valid(next_row, next_col) and (next_row, next_col) not in seen:
                    size += dfs(next_row, next_col)
            return size

        # do dfs on every node in the given graph
        for row in range(m):
            for col in range(n):
                if grid[row][col] == 1 and (row, col) not in seen:
                    area = max(dfs(row, col), area)

        return area

#time complexity: O(M*N)
#space complexity: O(M*N)