Number of Islands

You are given a rectangular map grid where each cell is the character "1" (land) or "0" (water). An island is a group of land cells connected to each other horizontally or vertically; land cells that only touch at a corner belong to different islands.

Return the number of islands on the map. Everything outside the grid counts as water.

Example 1

Example 2

Example 3

Constraints

• 1 <= m, n <= 100 (m rows, n columns)
• grid[i][j] is "0" or "1"

Pattern Path · Graphs: Traversal · problem 131 of 169

Start simple

For each land cell, run a search to collect its island and compare it with the islands found so far: O((mn)²) time.

The key idea

Treat the grid as a graph whose nodes are land cells and whose edges join land cells that share a side. Islands are then exactly the connected components, and counting components is a classic traversal task.

Scan every cell in row order. When you reach a land cell that has not been visited, increase the counter and flood-fill from it: use a queue (BFS) or stack (DFS) to visit every land cell reachable from it, marking each as visited as soon as it is added. When the fill finishes, the whole island is marked, so the scan will skip all of its other cells and the island is counted exactly once.

Marking can be done by overwriting the cell with "0" (sinking the island) or with a separate visited matrix if the input must stay unchanged. Each cell is added to the queue at most once and checks four neighbours, so the total work is linear in the grid size. An explicit queue or stack avoids hitting recursion limits on large, snake-shaped islands; union-find is another valid way to merge neighbouring land cells.

Complexity

• Time: O(m · n)
• Space: O(m · n) in the worst case for the queue

Python

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        rows, cols = len(grid), len(grid[0])
        islands = 0

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] != "1":
                    continue
                # New island found: sink all of it so it is counted only once.
                islands += 1
                grid[r][c] = "0"
                queue = deque([(r, c)])
                while queue:
                    i, j = queue.popleft()
                    for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                        if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == "1":
                            grid[ni][nj] = "0"  # mark when pushed, not when popped
                            queue.append((ni, nj))

        return islands

JavaScript

var numIslands = function(grid) {
  const rows = grid.length, cols = grid[0].length;
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  let islands = 0;

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] !== "1") continue;
      // New island found: sink all of it so it is counted only once.
      islands++;
      grid[r][c] = "0";
      const stack = [[r, c]];
      while (stack.length > 0) {
        const [i, j] = stack.pop();
        for (const [di, dj] of dirs) {
          const ni = i + di, nj = j + dj;
          if (ni >= 0 && ni < rows && nj >= 0 && nj < cols && grid[ni][nj] === "1") {
            grid[ni][nj] = "0"; // mark when pushed, not when popped
            stack.push([ni, nj]);
          }
        }
      }
    }
  }
  return islands;
};

What the interviewer is checking

It is the standard test of recognising connected components in a grid and writing a bug-free flood fill with correct bounds checks.

Mistakes to avoid

• Counting diagonal neighbours as connected.
• Marking cells visited only when they are popped instead of when they are pushed, so the same cell is queued many times.
• Comparing with the number 1 instead of the string "1".
• Deep recursion on a long winding island can overflow the stack.

Follow-ups to expect

• Return the size of the largest island? (Count cells during the fill.)
• Land is added one cell at a time; report counts after each? (Union-find.)
• Count islands with distinct shapes? (Normalised path signatures.)

In real software

Image processing labels connected regions (blobs) in a bitmap with this flood fill, and map software uses it to find contiguous areas like lakes or zones.

Practice next