The problem. You're given a grid of "1" (land) and "0" (water). An island is a group of land cells joined up, down, left or right; diagonals don't join. Return how many islands there are. Everything outside the grid is water.
grid = [["1","1","0","0","0"],
["1","1","0","0","1"],
["0","0","1","0","1"],
["0","0","0","1","1"]] -> 3
grid = [["1","1","1"],
["0","1","0"],
["1","1","1"]] -> 1 (all one shape)This is Flood Fill run many times. Scan the grid. Each time you land on a "1" that no walk has reached yet, you've found a new island: count it, then walk the whole island and sink it — turn its cells to "0" — so the scan never counts it again. The answer is the number of walks you started.
Sinking reuses the grid as the visited marker. If you mustn't change the input, keep a separate visited grid instead; nothing else changes.
Each new island gets counted, then sunk cell by cell. Try land that only touches diagonally.
function numIslands(grid) { const rows = grid.length, cols = grid[0].length; const sink = (r, c) => { if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== "1") return; // water or off the map grid[r][c] = "0"; // sink it, so no later scan counts it again sink(r - 1, c); sink(r + 1, c); sink(r, c - 1); sink(r, c + 1); }; let islands = 0; for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (grid[r][c] === "1") { // land no walk has reached: a new island islands++; sink(r, c); // sink the whole island } } } return islands;}Time O(m · n), space O(m · n). The scan looks at every cell once, and each land cell is sunk exactly once across all the walks — so the total is linear, however many islands there are. The recursion can be m · n deep if the whole grid is land.
The same count, with each island walked by a queue so the call stack never grows. Sink cells as they enter the queue.
const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]]; function numIslands(grid) { const rows = grid.length, cols = grid[0].length; let islands = 0; for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (grid[r][c] !== "1") continue; islands++; // a new island grid[r][c] = "0"; // sink on the way IN const queue = [[r, c]]; let head = 0; while (head < queue.length) { const [cr, cc] = queue[head++]; for (const [dr, dc] of DIRS) { 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]); } } } } } return islands;}Time O(m · n), space O(m · n) in the worst case. The queue only ever holds the island's moving edge, so in practice it stays much smaller — and there's no recursion to overflow.
[["1","0"],["0","1"]] is 2 islands.