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 defined as a maximal set of connected 1s.

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 maxArea to store the maximum area found so far, initialized to 0. Also, create a visited matrix of the same dimensions as the input grid to keep track of visited cells, initialized with all false values.

2. Iterate through the grid: Use nested loops to iterate through each cell of the grid.

3. Check for unvisited land: If a cell contains 1 (land) and hasn't been visited, call a Depth-First Search (DFS) function to explore the connected island.

4. Depth-First Search (DFS): The DFS function recursively explores the connected land cells. It takes the current row and column as input. For each valid neighbor (up, down, left, right), it checks if it's within bounds, contains 1 (land), and hasn't been visited. If all conditions are met, it recursively calls itself on the neighbor, marking the cell as visited and incrementing the area.

5. Update maxArea: After the DFS completes for an island, the area is returned. Update maxArea if the current island's area is larger.

6. Return maxArea: After iterating through the entire grid, return the maxArea.

Explanation:

The algorithm uses Depth-First Search (DFS) to explore connected components in the grid. DFS is suitable because it efficiently explores all connected land cells starting from a single unvisited land cell. The visited matrix prevents revisiting cells and ensures that each island is counted only once. The maximum area is tracked throughout the process.

Code:

function maxAreaOfIsland(grid: number[][]): number {
    let maxArea = 0;
    const rows = grid.length;
    const cols = grid[0].length;
    const visited = Array.from(Array(rows), () => Array(cols).fill(false));

    const dfs = (row: number, col: number): number => {
        if (row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] === 0 || visited[row][col]) {
            return 0;
        }
        visited[row][col] = true;
        return 1 + dfs(row + 1, col) + dfs(row - 1, col) + dfs(row, col + 1) + dfs(row, col - 1);
    };

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (grid[i][j] === 1 && !visited[i][j]) {
                maxArea = Math.max(maxArea, dfs(i, j));
            }
        }
    }
    return maxArea;
};

Complexity:

• Time Complexity: O(M * N), where M and N are the dimensions of the grid. Each cell is visited at most once.
• Space Complexity: O(M * N) in the worst case, due to the visited matrix. The recursion depth of DFS is at most the minimum of M and N.