Number of islands
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
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;}