Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumgraph-dfs

Max Area of Island

Problem (restated)

Given a grid of 0 (water) and 1 (land), an island is a 4-directionally connected group of 1s. Return the area of the largest island, or 0 if there is no land.

Intuition

LC 200 counts how many times you start a flood fill. Here each fill returns how many cells it painted. Keep the max.

Approaches

DFS area

Unverified

Time O(m·n)Space O(m·n) worst-case stack

Idea. On land, DFS returns 1 + the four recursive calls, marking the cell 0 so it is not recounted. Scan the grid; best = max(best, dfs(r, c)).

Walkthrough. Two islands of size 1 and 3 → 3. All water → 0.

Trade-offs. Mutating the grid is O(1) extra besides the stack. A visited matrix is the same if you must not mutate. Each cell is entered once, so time is linear in the grid.

Solution

export function maxAreaOfIsland(grid: number[][]): number {
  if (!grid.length) return 0;
  const m = grid.length, n = grid[0]!.length;
  const dfs = (r: number, c: number): number => {
    if (r < 0 || c < 0 || r >= m || c >= n || grid[r]![c] === 0) return 0;
    grid[r]![c] = 0;
    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;
}

export function maxAreaOfIsland(grid: number[][]): number {
  if (!grid.length) return 0;
  const m = grid.length, n = grid[0]!.length;
  const dfs = (r: number, c: number): number => {
    if (r < 0 || c < 0 || r >= m || c >= n || grid[r]![c] === 0) return 0;
    grid[r]![c] = 0;
    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;
}

Template connection

Flood-fill shape of Graph DFS, with the DFS returning a count instead of void. Same skeleton as LC 733 / LC 200.

Reflection

On a land cell, count 1 plus the four neighbors and set the cell to 0. The answer is the largest component. Four directions only.
Without the mark the same island is counted twice. A diagonal neighbor is a different island.
No land is 0. One cell is 1. A grid of all land is m * n.