[link](https://leetcode.com/problems/max-area-of-island/)

---

You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (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 grid. If there is no island, return 0.

#### Example 1:


Input: grid = [[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]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.

#### Example 2:

Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0

#### Constraints:

- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 50
- grid[i][j] is either 0 or 1.

---

The initial check if not grid: ensures that the grid is not empty. If it is empty, the function returns 0. The islands_area variable is initialized to 0, which will store the maximum area of an island found.

The visit set is used to keep track of visited cells to avoid processing them multiple times. The dfs function is a helper function that performs a depth-first search on the grid starting from a given cell (r, c) and returns the area of the island connected to that cell. Inside the dfs function, the conditions to terminate the DFS recursion are as follows:

If the current cell is out of bounds (r or c is less than 0 or equal to the length of the grid). If the current cell has been visited before. If the current cell contains 0, indicating it is not part of an island. If the current cell satisfies the above conditions, the function simply returns 0.

If the current cell is a valid part of an island, it is marked as visited by adding (r, c) to the visit set. The DFS recursion continues by calling dfs on the adjacent cells: (r + 1, c), (r - 1, c), (r, c + 1), and (r, c - 1). The area of the island connected to the current cell is calculated as 1 plus the sum of the areas of the islands connected to its adjacent cells.

After the dfs function, a nested loop is used to iterate over each cell in the grid. If the current cell has not been visited and contains 1, it means a new island has been found. The dfs function is called starting from this cell, and the resulting area is stored in the area variable.

The islands_area is updated to the maximum value between islands_area and area, ensuring that the maximum area of an island is always stored.

#### Solution 1

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0

        islands_area = 0
        visit = set()

        def dfs(r: int, c: int) -> int:
            if (min(r, c) < 0 or
                r == len(grid) or
                c == len(grid[0]) or
                (r, c) in visit or
                grid[r][c] == 0):
                return 0

            visit.add((r, c))
            return (1 + dfs(r + 1, c) + 
                        dfs(r - 1, c) + 
                        dfs(r, c + 1) +
                        dfs(r, c - 1))


        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if (r, c) not in visit and grid[r][c] == 1:
                    area = dfs(r, c)
                    islands_area = max(islands_area, area)

        return islands_area
        

O(T): O(n * m)
O(S): O(n * m)