Max Area of Island

Share

Find the maximum area of an island in a 2D grid (4-directionally connected 1s).

Example 1
Input: grid (see standard Max Area of Island grid) → Output: 6
Example 2
Input: grid=[[0,0,0,0,0,0,0,0]] → Output: 0

Solution Approach

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
Java
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)