Number of Islands
MediumGraphs
You get a map as a grid of one-letter strings: "1" is land and "0" is water. An island is a group of land cells joined up, down, left or right (not diagonally), and everything outside the grid is water.
Return how many islands the map has. On this page a grid is written as an array of rows, top row first, so grid[r][c] is row r, column c.
Examples
Input: grid = [["1", "1", "0", "0", "1"], ["1", "0", "0", "1", "1"], ["0", "0", "1", "0", "0"], ["0", "0", "0", "0", "1"]] Output: 4
The three cells top left, the three top right, the lone 1 in the middle and the one bottom right.
Input: grid = [["1", "1", "1"], ["0", "1", "0"], ["1", "1", "1"]] Output: 1
The middle column joins the top row to the bottom row, so it is all one island.
Constraints
1 ≤ m, n ≤ 300for a grid of m rows and n columns- Every cell is
"0"or"1".
Stuck?
Hint 1
Scan the grid. Each land cell you reach that is not yet part of a counted island starts a new one.
Hint 2
When you start an island, flood it: DFS or BFS through every land cell joined to it, marking each as seen (or turning it to "0"), so the scan never counts it again.
The idea
Scan the grid cell by cell. Each time you reach land that no earlier island has claimed, you have found a new island. Count it, then flood out from that cell and sink all the land joined to it, so no part of it is counted again.
Time O(m · n)Extra space O(m · n) in the worst case, for the flood’s stack or queue
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 5
sink floods one island. It stops at the edge of the grid and at any cell that is not land: water, or land it has already sunk.
function numIslands(grid) { const rows = grid.length; const cols = grid[0].length; const sink = (r, c) => { if (r < 0 || r >= rows || c < 0 || c >= cols || 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); }; let count = 0; for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (grid[r][c] === '1') { count++; sink(r, c); } } } return count;}The trap
Spreading only down and to the right misses land that bends up or to the left. That part of the island is never sunk, so the scan reaches it later and counts it as a second island.
function numIslands(grid) { const sink = (r, c) => { if (r >= grid.length || c >= grid[0].length || grid[r][c] !== '1') return; grid[r][c] = '0'; sink(r + 1, c); // spreads only down and right, so an island that bends up or left is counted twice sink(r, c + 1); }; let count = 0; for (let r = 0; r < grid.length; r++) { for (let c = 0; c < grid[0].length; c++) { if (grid[r][c] === '1') { count++; sink(r, c); } } } return count;}