Pattern Guide
Grid Island Problems
"Connected components in grids. BFS/DFS flood fill, area, perimeter, enclosure."
Grid island problems find, count, measure, or transform connected regions of cells. Core technique: BFS or DFS flood fill — visit connected cells of the same type, marking them visited. Patterns: count islands (DFS from each unvisited land cell), max area (track count during DFS), perimeter (count edges facing water), number of closed islands (flood fill from borders, then count remaining), and surrounded regions (O-cells not connected to border).
Problems you can solve with this pattern
4 problems · click any to start solving
// Number of islands — DFS flood fill
function numIslands(grid) {
const m = grid.length, n = grid[0].length;
let count = 0;
function dfs(r, c) {
if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] !== '1') return;
grid[r][c] = '0'; // mark visited
dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1);
}
for (let r = 0; r < m; r++)
for (let c = 0; c < n; c++)
if (grid[r][c] === '1') { dfs(r, c); count++; }
return count;
}
// Max area of island
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 r = 0; r < m; r++)
for (let c = 0; c < n; c++)
if (grid[r][c] === 1) max = Math.max(max, dfs(r, c));
return max;
}Flood fill: from any unvisited cell, BFS/DFS marks all connected same-value cells as visited. Number of flood fills = number of connected components. Perimeter of an island: for each land cell, count edges where neighbor is water or out-of-bounds (4 - connected land neighbors). Enclosed regions: flood fill from border to mark "safe" cells; remaining unvisited cells are enclosed.
// Number of islands — DFS flood fill
function numIslands(grid) {
const m = grid.length, n = grid[0].length;
let count = 0;
function dfs(r, c) {
if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] !== '1') return;
grid[r][c] = '0'; // mark visited
dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1);
}
for (let r = 0; r < m; r++)
for (let c = 0; c < n; c++)
if (grid[r][c] === '1') { dfs(r, c); count++; }
return count;
}
// Max area of island
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 r = 0; r < m; r++)
for (let c = 0; c < n; c++)
if (grid[r][c] === 1) max = Math.max(max, dfs(r, c));
return max;
}- Count islands: DFS/BFS from each unvisited land cell, count starts
- Max area: return size from DFS, track max
- Perimeter: for each land cell, 4 - count(land neighbors)
- Closed/enclosed: flood fill from borders first to mark unreachable cells
BFS vs DFS for grids: DFS is simpler (recursive) but can stack overflow on large grids. BFS (queue-based) is always safe. For very large grids (m*n > 10^5), use iterative BFS.
Union-Find alternative: For dynamic connectivity (edges added), Union-Find tracks components efficiently. For static grids, DFS/BFS is simpler.