Count the connected components of "1" cells in a binary grid by BFS flood-filling each unvisited land cell — the moment you discover a new 1without visiting it first, you've found a new island.
Given a 2-D grid of "1" (land) and "0" (water), count the number of islands. An island is a group of horizontally or vertically connected land cells, surrounded by water or grid boundaries.
Example:["1","1","0","0"]["1","1","0","0"]["0","0","1","0"]["0","0","0","1"]
→ output 3. Top-left 2×2 block is island 1; the lone cell at (2,2) is island 2; the lone cell at (3,3) is island 3.
"1", increment the counter once and immediately flood-fill the entire connected component, marking every reachable land cell visited. The next unvisited "1" your scan finds is guaranteed to belong to a brand-new island — no merging, no double-counting.(r, c) in row-major order. This ensures no cell is ever skipped.grid[r][c] === '1' and not yet visited, this is a new island. Increment count.(r, c) and mark it visited immediately. For each dequeued cell, check its 4 neighbors; enqueue any unvisited land neighbor and mark it visited right away (before it is dequeued) to prevent duplicate enqueues.'0' in-place (O(1) space), or use a separate visited boolean grid (safer if the input must not be mutated).Both BFS and DFS give identical complexity. BFS uses a queue (iterative, no call-stack risk); DFS is slightly shorter to write but can blow the call stack on grids that are entirely land. Union-Find is a third option that gives the same O(R·C·α) asymptotic (practically O(R·C)) and is useful when the grid is updated dynamically (see Number of Islands II).
function numIslands(grid: string[][]): number {
const rows = grid.length;
const cols = grid[0].length;
let count = 0;
function bfs(r: number, c: number): void {
const queue: [number, number][] = [[r, c]];
grid[r][c] = '0'; // mark visited in-place
const dirs: [number, number][] = [[-1,0],[1,0],[0,-1],[0,1]];
while (queue.length > 0) {
const [cr, cc] = queue.shift()!;
for (const [dr, dc] of dirs) {
const nr = cr + dr;
const nc = cc + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === '1') {
grid[nr][nc] = '0'; // mark before enqueue prevents duplicates
queue.push([nr, nc]);
}
}
}
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === '1') {
count++;
bfs(r, c);
}
}
}
return count;
}rows and cols once so every bounds check is a simple comparison.'0'. The inner loop dequeues, checks all four neighbors, and marks + enqueues any unvisited land. Marking on enqueue (line 15) prevents the same cell from entering the queue via two different neighbors.'1' is found, the counter increments once and the BFS erases the whole island. No cell will ever trigger the counter twice.count equals the number of connected components. The grid has been flattened to all '0's as a side effect (in-place mutation).visited: boolean[][] array initialized to false. Same complexity; no side effects.'1' do a fresh DFS without marking — O((R·C)²) in the worst case. The flood-fill brings it to O(R·C) by guaranteeing each cell is touched at most once.| "count connected regions" in a grid | BFS/DFS flood fill + visited set |
| grid of 0/1 with 4-directional adjacency | outer scan → fill on unvisited 1 |
| "islands update dynamically / streaming cells" | Union-Find with running count |
| "area of each island" instead of count | same fill, return cell count |
function numIslands(grid: string[][]): number {
const rows = grid.length, cols = grid[0].length;
let count = 0;
function bfs(r: number, c: number): void {
const queue: [number, number][] = [[r, c]];
grid[r][c] = '0';
while (queue.length > 0) {
const [cr, cc] = queue.shift()!;
for (const [dr, dc] of [[-1,0],[1,0],[0,-1],[0,1]] as [number,number][]) {
const nr = cr + dr, nc = cc + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === '1') {
grid[nr][nc] = '0';
queue.push([nr, nc]);
}
}
}
}
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++)
if (grid[r][c] === '1') { count++; bfs(r, c); }
return count;
}R × C grid?["1","1","0","0"]["1","1","0","0"]["0","0","1","0"]["0","0","0","1"]"1"s (every cell is land). How many islands are there?