Skip to main content

25. Max Area of Island

mediumAsked at GitHub

Find the largest connected component in a binary grid using DFS — the same connected-components analysis used when GitHub calculates the largest contiguous change region in a pull request diff.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a binary matrix grid of 0s and 1s, find and return the maximum area of an island (connected 1s touching horizontally or vertically). Return 0 if no island exists.

Constraints

  • m == grid.length, n == grid[i].length
  • 1 <= m, n <= 50
  • grid[i][j] is 0 or 1

Examples

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],...(4x13)]
Output
6

Example 2

Input
grid = [[0,0,0,0,0,0,0,0]]
Output
0

Approaches

1. BFS counting visited set

BFS from each unvisited 1, count nodes reached — correct but uses extra visited set memory.

Time
O(m*n)
Space
O(m*n)
// visited Set; BFS from each '1'; count queue pops; update max
// Correct but extra space for visited

Tradeoff:

2. DFS with in-place zeroing

DFS from each unvisited 1, set cells to 0 as visited, accumulate count. Return 1 + recursive sums of 4 neighbors. Track global max.

Time
O(m*n)
Space
O(m*n) stack
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]===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 max = 0;
  for (let i=0;i<m;i++) for (let j=0;j<n;j++) if (grid[i][j]===1) max=Math.max(max,dfs(i,j));
  return max;
}

Tradeoff:

GitHub-specific tips

GitHub graph problems often follow up by asking how to handle the same computation on streaming grid updates; mention Union-Find as an extension for dynamic connectivity without full re-traversal.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Max Area of Island and other GitHub interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →