Number of islands

Medium

Problem

In a grid of "1" (land) and "0" (water), an island is a group of land cells connected up, down, left or right. Return the number of islands.

Example 1

Input:  [["1","1","0","0"], ["1","1","0","0"], ["0","0","1","0"], ["0","0","0","1"]]
Output: 3

Also asked as: Find the no. of Isalnds · Find the no. of Islands

Test cases

Case 1

Input:    [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
Expected: 1

Case 2

Input:    [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
Expected: 3

Case 3

Input:    [["0"]]
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution2 approaches

1. DFS flood fill

Time O(R·C)Space O(R·C) recursion worst case

Scan the grid; each unvisited land cell starts a new island — sink its whole component.

function numIslands(grid) {
const R = grid.length, C = grid[0].length;
let count = 0;
const sink = (r, c) => {
if (r < 0 || c < 0 || r >= R || c >= C || grid[r][c] !== '1') return;
grid[r][c] = '0';
sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1);
};
for (let r = 0; r < R; r++)
for (let c = 0; c < C; c++)
if (grid[r][c] === '1') { count++; sink(r, c); }
return count;
}

2. BFS flood fill

Time O(R·C)Space O(min(R,C))

Same idea, queue instead of recursion — avoids deep stacks on huge grids.

function numIslands(grid) {
const R = grid.length, C = grid[0].length;
let count = 0;
const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
for (let r = 0; r < R; r++)
for (let c = 0; c < C; c++)
if (grid[r][c] === '1') {
count++;
const q = [[r, c]]; grid[r][c] = '0';
while (q.length) {
const [x, y] = q.shift();
for (const [dx, dy] of dirs) {
const nx = x + dx, ny = y + dy;
if (nx >= 0 && ny >= 0 && nx < R && ny < C && grid[nx][ny] === '1') {
grid[nx][ny] = '0'; q.push([nx, ny]);
}
}
}
}
return count;
}