Find the maximum area of an island in a 2D grid (4-directionally connected 1s).
Input: grid (see standard Max Area of Island grid) → Output: 6
Input: grid=[[0,0,0,0,0,0,0,0]] → Output: 0
DFS from each unvisited land cell, counting connected cells.
- Iterate all cells
- For unvisited land cell (1): DFS and count area
- Mark visited during DFS by setting to 0
- Track maximum area found
public int maxAreaOfIsland(int[][] grid) {
int max = 0;
for (int i = 0; i < grid.length; i++)
for (int j = 0; j < grid[0].length; j++)
if (grid[i][j] == 1) max = Math.max(max, dfs(grid, i, j));
return max;
}
private int dfs(int[][] grid, int i, int j) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) return 0;
grid[i][j] = 0;
return 1 + dfs(grid,i+1,j) + dfs(grid,i-1,j) + dfs(grid,i,j+1) + dfs(grid,i,j-1);
}
- Time Complexity: O(m*n)
- Space Complexity: O(m*n)