Pattern Reference
Grid Islands
"Number of islands, max area island, number of distinct islands, surrounded regions."
Loading...
Deep Dive Tutorial
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 and max area templates
// 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;
}Worked Problems
mountain
Grid island patterns:
- 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.
- 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.