Max Area of Island medium

Problem Statement

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.

Find the maximum area of an island in the given grid. An island is one or more connected 1s (horizontally or vertically).

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

Steps

1. Initialization: Create a variable max_area to store the maximum area found so far, initializing it to 0.
2. Iteration: Iterate through each cell of the grid.
3. Island Detection: If a cell contains '1' (land) and hasn't been visited yet:
   • Call a Depth-First Search (DFS) function to explore the connected land cells.
   • Update max_area if the area of the current island is greater.
4. Depth-First Search (DFS): The DFS function recursively explores the connected land cells, marking visited cells as '0' to avoid revisiting them. It returns the area of the island.
5. Return: After iterating through the entire grid, return max_area.

Explanation

The solution uses Depth-First Search (DFS) to explore each connected component of land (island) in the grid. DFS is ideal for exploring connected components because it systematically explores all reachable nodes from a starting point. By marking visited cells as '0', we prevent double-counting cells and ensure we only count the area of each distinct island once.

The dfs function recursively explores the adjacent cells (up, down, left, right). It adds 1 to the area count for each land cell it visits. The base cases for recursion are: hitting water ('0'), going out of bounds, or encountering a visited cell ('0').

Code

def maxAreaOfIsland(grid):
    """
    Finds the maximum area of an island in a given grid.

    Args:
        grid: A list of lists representing the grid.

    Returns:
        The maximum area of an island.
    """
    rows, cols = len(grid), len(grid[0])
    max_area = 0

    def dfs(row, col):
        """
        Performs Depth-First Search to explore an island.
        """
        if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] == 0:
            return 0  # Base case: water, out of bounds, or visited cell
        grid[row][col] = 0  # Mark cell as visited
        area = 1 + dfs(row + 1, col) + dfs(row - 1, col) + dfs(row, col + 1) + dfs(row, col - 1)
        return area

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                max_area = max(max_area, dfs(r, c))

    return max_area

Complexity

• Time Complexity: O(M*N), where M and N are the dimensions of the grid. In the worst case, we visit each cell once.
• Space Complexity: O(M*N) in the worst case, due to the recursive calls in DFS. The maximum depth of the recursion stack could be equal to the number of cells in the largest island. In practice, this space complexity can be considered relatively small compared to the input size. We could also optimize it to use an iterative approach with a stack, reducing the space complexity to O(max(M,N)).