Intermediate LevelData Structures & Algorithms
How do you count the Number of Islands in a 2D grid?
ā Interview Prompt: Count connected components (islands) in a binary grid using DFS/BFS flooding in O(MĆN) time.
Approach: Iterate every cell. When a '1' (land) is found, increment island count and run DFS/BFS to flood-fill (mark) all connected land cells as '0' (visited) to prevent recounting.
ā¢
Time: $O(M \times N)$ ā each cell is visited at most once.
ā¢
Space: $O(M \times N)$ worst case (recursion stack for DFS on a grid full of '1').
Code Implementation Example
typescript
function numIslands(grid: string[][]): number {
const rows = grid.length, cols = grid[0].length;
let count = 0;
function dfs(r: number, c: number): void {
if (r < 0 || c < 0 || r >= rows || c >= cols || 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 < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === '1') {
count++;
dfs(r, c); // flood fill island
}
}
}
return count;
}š”Number of Islands using DFS flood-fill ā O(MĆN) time.
šÆ Interview Key Takeaway
Number of Islands is a classic connected-component counting problem. The DFS/BFS flood-fill pattern extends to: clone graph, Pacific Atlantic water flow, and word search.
#DSA#Graph#DFS#BFS#Grid#Intermediate
Back to all Data Structures & Algorithms Questionsā