Number of Islands Solutions & Complexity

1. Define the problem

Number of Islands

Given an m x n grid of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and formed by connecting adjacent lands horizontally or vertically . Scan every cell; whenever you find unvisited land, that is a new island — run depth-first search from it to mark every connected land cell so you never count the same island twice.

Constraints

m == grid.length
n == grid_i.length
1 ≤ m, n ≤ 300
grid_i[j] is '0' or '1'

Example

Inputgrid = [['1','1','0','0','0'],['1','1','0','0','0'],['0','0','1','0','0'],['0','0','0','1','1']]

Output3

Explanation There are three separate connected groups of land: the top-left block, the single cell in the middle, and the two cells in the bottom-right corner.

2. Know the words first

In plain terms

Connected component: A group of cells that can all reach each other by stepping between neighboring land cells — one island.

3. Visualize the solution

Flood fill each new island, counting as you go

Statusstart scan

(0,0) = '1' and unvisited — start a new island, island #1.

What happens in this step

scan finds index 0  →  grid[0] = '1', not yet visited

Increment island count to 1, then start dfs(row 0, col 0) to mark every land cell reachable from here.

Step 1 of 4

Steps to visualize

Scan the grid in row-major order.
On finding unvisited land, increment the island count and start a depth-first search from that cell.
The search marks every reachable land cell as visited so the outer scan skips it later.
Continue scanning — the next unvisited land cell starts a new island.
The final count is the number of separate connected regions.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Flood fill each new island, counting as you go

Statusstart scan

(0,0) = '1' and unvisited — start a new island, island #1.

What happens in this step

scan finds index 0  →  grid[0] = '1', not yet visited

Increment island count to 1, then start dfs(row 0, col 0) to mark every land cell reachable from here.

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

function numIslands(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  const visited = grid.map((row) => row.map(() => false));

  function dfs(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    if (visited[r][c] || grid[r][c] !== '1') return;

    visited[r][c] = true;
    dfs(r + 1, c);
    dfs(r - 1, c);
    dfs(r, c + 1);
    dfs(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' && !visited[r][c]) {
        count++;
        dfs(r, c);
      }
    }
  }

  return count;
}

Time: O(rows × cols)
Space: O(rows × cols)

6. Test cases

Test cases

Input	Expected	Covers
`grid = [['1','1','0','0','0'],['1','1','0','0','0'],['0','0','1','0','0'],['0','0','0','1','1']]`	`3`	example from the docstring
`grid = [['0','0'],['0','0']]`	`0`	grid entirely water
`grid = [['1','1'],['1','1']]`	`1`	grid entirely land, one connected island
`grid = [['1']]`	`1`	smallest valid input, a single land cell
`grid = [['0']]`	`0`	smallest valid input, a single water cell
`grid = [['1','0'],['0','1']]`	`2`	diagonal land cells do not count as one island
`grid = [['1','0','1','0','1']]`	`3`	several single-cell islands in one row
`grid = [['1','1','1'],['0','0','1'],['1','1','1']]`	`1`	a winding shape that is nonetheless a single connected island

Number of Islands