given an two dimensional binary matrix grid an island is a group of 1 s representing land connected 4directionally horizontal or vertical you may assume all four edges of the grid are surrounded by water the area of an island is the number of cells with a value 1 in the island return the maximum area of an island in a grid if there is no island return 0 checking whether coordinate row col is valid or not issafe0 0 5 5 true issafe1 1 5 5 false returns the current area of the island depthfirstsearch0 0 set matrix 0 finds the area of all islands and returns the maximum area findmaxareamatrix 6 maximizing the area explanation we are allowed to move in four directions horizontal or vertical so the possible in a matrix if we are at x and y position the possible moving are directions are x y1 x y1 x1 y x1 y but we need to take care of boundary cases as well which are x and y can not be smaller than 0 and greater than the number of rows and columns respectively visualization mat 0 0 a 0 0 0 0 b 0 0 0 0 0 0 0 0 0 0 0 0 b b b 0 0 0 0 c c 0 d 0 0 0 0 0 0 0 0 0 c 0 0 d d 0 0 e 0 e 0 0 0 c 0 0 d d 0 0 e e e 0 0 0 0 0 0 0 0 0 0 0 0 e 0 0 0 0 0 0 0 0 0 f f f 0 0 0 0 0 0 0 0 0 0 f f 0 0 0 0 for visualization i have defined the connected island with letters by observation we can see that a island is of area 1 b island is of area 4 c island is of area 4 d island is of area 5 e island is of area 6 and f island is of area 5 it has 6 unique islands of mentioned areas and the maximum of all of them is 6 so we return 6 checking whether coordinate row col is valid or not is_safe 0 0 5 5 true is_safe 1 1 5 5 false returns the current area of the island depth_first_search 0 0 set matrix 0 finds the area of all islands and returns the maximum area find_max_area matrix 6 maximizing the area output 6 explanation we are allowed to move in four directions horizontal or vertical so the possible in a matrix if we are at x and y position the possible moving are directions are x y 1 x y 1 x 1 y x 1 y but we need to take care of boundary cases as well which are x and y can not be smaller than 0 and greater than the number of rows and columns respectively visualization mat 0 0 a 0 0 0 0 b 0 0 0 0 0 0 0 0 0 0 0 0 b b b 0 0 0 0 c c 0 d 0 0 0 0 0 0 0 0 0 c 0 0 d d 0 0 e 0 e 0 0 0 c 0 0 d d 0 0 e e e 0 0 0 0 0 0 0 0 0 0 0 0 e 0 0 0 0 0 0 0 0 0 f f f 0 0 0 0 0 0 0 0 0 0 f f 0 0 0 0 for visualization i have defined the connected island with letters by observation we can see that a island is of area 1 b island is of area 4 c island is of area 4 d island is of area 5 e island is of area 6 and f island is of area 5 it has 6 unique islands of mentioned areas and the maximum of all of them is 6 so we return 6
matrix = [
    [0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
    [0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0],
    [0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0],
]


def is_safe(row: int, col: int, rows: int, cols: int) -> bool:
    
    return 0 <= row < rows and 0 <= col < cols


def depth_first_search(row: int, col: int, seen: set, mat: list[list[int]]) -> int:
    
    rows = len(mat)
    cols = len(mat[0])
    if is_safe(row, col, rows, cols) and (row, col) not in seen and mat[row][col] == 1:
        seen.add((row, col))
        return (
            1
            + depth_first_search(row + 1, col, seen, mat)
            + depth_first_search(row - 1, col, seen, mat)
            + depth_first_search(row, col + 1, seen, mat)
            + depth_first_search(row, col - 1, seen, mat)
        )
    else:
        return 0


def find_max_area(mat: list[list[int]]) -> int:
    
    seen: set = set()

    max_area = 0
    for row, line in enumerate(mat):
        for col, item in enumerate(line):
            if item == 1 and (row, col) not in seen:
                
                max_area = max(max_area, depth_first_search(row, col, seen, mat))
    return max_area


if __name__ == "__main__":
    import doctest

    print(find_max_area(matrix))  

    

    doctest.testmod()