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 surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are surrounded by water.

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.
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 island.
4. Depth-First Search (DFS): The DFS function recursively explores the island by marking visited cells as 0 and counting the area. It explores horizontally and vertically adjacent cells.
5. Area Update: After DFS completes for an island, update maxArea if the current island's area is greater.
6. Return: Return maxArea.

Explanation

The solution uses Depth-First Search (DFS) to efficiently explore connected components (islands) in the grid. The DFS function recursively explores the island, marking visited cells as 0 to avoid revisiting them. The recursive calls ensure that all connected land cells are included in the area calculation for each island.

Code

public class Solution {
    public int MaxAreaOfIsland(int[][] grid) {
        int m = grid.Length;
        int n = grid[0].Length;
        int maxArea = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int area = Dfs(grid, i, j);
                    maxArea = Math.Max(maxArea, area);
                }
            }
        }
        return maxArea;
    }

    private int Dfs(int[][] grid, int i, int j) {
        int m = grid.Length;
        int n = grid[0].Length;

        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) {
            return 0;
        }

        grid[i][j] = 0; // Mark as visited

        return 1 + Dfs(grid, i + 1, j) + Dfs(grid, i - 1, j) + Dfs(grid, i, j + 1) + Dfs(grid, i, j - 1);
    }
}

Complexity

• Time Complexity: O(M * N), where M and N are the dimensions of the grid. We visit each cell at most once.
• Space Complexity: O(M * N) in the worst case, due to the recursive calls of DFS which might reach the maximum depth of the grid in case of a large connected island. In practice, it's often less due to the visited cells being marked as 0.