Max Area of Island

medium array dfs matrix

Problem

Given a 2D binary grid where 1 = land, 0 = water, return the maximum area (number of cells) of an island. An island is a 4-directionally connected group of 1s.

Inputgrid = [[1,1,0],[1,0,0],[0,0,1]]

Output3

Top-left island has 3 cells; bottom-right island has 1.

grid (rows separated by ';', cells by ',')

def max_area_of_island(grid):
    m, n = len(grid), len(grid[0])
    def dfs(r, c):
        if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] != 1:
            return 0
        grid[r][c] = -1
        return 1 + dfs(r+1, c) + dfs(r-1, c) + dfs(r, c+1) + dfs(r, c-1)
    best = 0
    for r in range(m):
        for c in range(n):
            if grid[r][c] == 1:
                best = max(best, dfs(r, c))
    return best

function maxAreaOfIsland(grid) {
  const m = grid.length, n = grid[0].length;
  function dfs(r, c) {
    if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] !== 1) return 0;
    grid[r][c] = -1;
    return 1 + dfs(r+1, c) + dfs(r-1, c) + dfs(r, c+1) + dfs(r, c-1);
  }
  let best = 0;
  for (let r = 0; r < m; r++) for (let c = 0; c < n; c++)
    if (grid[r][c] === 1) best = Math.max(best, dfs(r, c));
  return best;
}

class Solution {
    int[][] g; int m, n;
    public int maxAreaOfIsland(int[][] grid) {
        g = grid; m = grid.length; n = grid[0].length; int best = 0;
        for (int r = 0; r < m; r++) for (int c = 0; c < n; c++)
            if (g[r][c] == 1) best = Math.max(best, dfs(r, c));
        return best;
    }
    int dfs(int r, int c) {
        if (r < 0 || r >= m || c < 0 || c >= n || g[r][c] != 1) return 0;
        g[r][c] = -1;
        return 1 + dfs(r+1, c) + dfs(r-1, c) + dfs(r, c+1) + dfs(r, c-1);
    }
}

int m, n;
int dfs(vector<vector<int>>& g, int r, int c) {
    if (r < 0 || r >= m || c < 0 || c >= n || g[r][c] != 1) return 0;
    g[r][c] = -1;
    return 1 + dfs(g, r+1, c) + dfs(g, r-1, c) + dfs(g, r, c+1) + dfs(g, r, c-1);
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
    m = grid.size(); n = grid[0].size(); int best = 0;
    for (int r = 0; r < m; r++) for (int c = 0; c < n; c++)
        if (grid[r][c] == 1) best = max(best, dfs(grid, r, c));
    return best;
}

Explanation

An island is just a blob of connected 1s. To find the biggest one, we scan the grid and whenever we hit a land cell we have not seen, we flood it with DFS to measure its full size.

The dfs(r, c) function returns the area of the island starting at that cell. It returns 0 if the cell is off the grid or not land, otherwise it marks the cell visited by setting grid[r][c] = -1 and adds 1 plus the areas of its four neighbors.

Marking visited in place is the key trick: it stops us from counting the same cell twice and saves a separate visited array. Each cell is touched once, so the whole thing is O(m·n).

In the main loops we call dfs from every remaining land cell and keep the largest area in best.

Example: grid = [[1,1,0],[1,0,0],[0,0,1]]. DFS from the top-left blob counts 3 connected cells; the lone cell at the bottom-right counts 1. So best = 3.

Time: O(m·n) Space: O(m·n)