Number of Islands: BFS and DFS in Python and TypeScript

The Number of Islands Problem

You are given a grid of "1"s (land) and "0"s (water). An island is a group of land cells connected horizontally or vertically, not diagonally. Count the islands. You can assume everything outside the grid is water.

Example 1

Input:
11110
11010
11000
00000
Output: 1
Why: every land cell connects to the others through some path of up, down, left and right moves.

Example 2

Input:
11000
11000
00100
00011
Output: 3
Why: the top-left block, the single cell in the middle and the bottom-right pair are not connected to each other.

Assumptions to confirm

• Do diagonal neighbours count as connected? (Usually not; it changes the answer.)
• May I modify the grid to mark visited cells, or must I leave it unchanged?
• How large can the grid be? (Very large grids can overflow a recursive call stack.)

Start With the Idea, Not the Optimisation

There is no slow brute force worth coding here. The real question is how to avoid counting the same island twice. The plan is: scan the grid, and the first time you meet a land cell that has not been visited, you have found a new island. Then visit every cell connected to it so the scan skips them later.

That second step is a flood fill, the same idea as the paint bucket in a drawing program, and it is a graph search. Treat each cell as a node with up to four neighbours and use breadth-first search (a queue) or depth-first search (recursion or a stack). Say out loud that the grid is a graph; interviewers want to hear that you recognise it.

The Optimal Approach: Scan and Flood Fill

Number of Islands Solution in Python and TypeScript

Both versions use breadth-first search and mark visited cells by changing them to "0", which avoids a separate visited set.

Python

from collections import deque


def num_islands(grid: list[list[str]]) -> int:
    if not grid:
        return 0
    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
            islands += 1
            grid[r][c] = "0"  # mark visited when queued
            queue = deque([(r, c)])
            while queue:
                cr, cc = queue.popleft()
                for nr, nc in ((cr + 1, cc), (cr - 1, cc), (cr, cc + 1), (cr, cc - 1)):
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1":
                        grid[nr][nc] = "0"
                        queue.append((nr, nc))
    return islands

TypeScript

function numIslands(grid: string[][]): number {
  if (grid.length === 0) return 0;
  const rows = grid.length;
  const 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;
      islands++;
      grid[r][c] = "0"; // mark visited when queued
      const queue: [number, number][] = [[r, c]];
      for (let head = 0; head < queue.length; head++) {
        const [cr, cc] = queue[head];
        for (const [dr, dc] of dirs) {
          const nr = cr + dr;
          const 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;
}

If you must not change the input, keep a set or a boolean grid of visited cells instead. A recursive depth-first version is shorter to write, but a large island can exceed the recursion limit, which is a good trade-off to mention.

Time and Space Complexity

How to Talk Through Number of Islands in an Interview

A strong spoken answer follows the same five beats every time:

1. Clarify: "Are diagonals connected? Can I modify the grid? How big can it be?"
2. Brute force: "The core idea is to count each island once: scan the grid, and when I find new land, visit everything connected to it."
3. Optimise: "That visiting step is a graph search on the grid. Breadth-first search with a queue avoids deep recursion, and each cell is processed once."
4. Code: point out where you mark cells as visited and why it happens when a cell is queued.
5. Test: run both example grids, then an empty grid, a single land cell and a checkerboard pattern. State O(rows × cols) time.

Explaining why you chose breadth-first over recursive depth-first search, and what happens with a huge island, is the kind of trade-off that lifts an answer from correct to strong.

Edge Cases and Common Follow-Ups

Practise Number of Islands in a Mock Coding Round

Number of Islands is a favourite because it tests whether you recognise a graph problem in disguise. Under interview pressure, candidates often lose time on the visited-marking bug or forget to clarify diagonals. Rehearsing it out loud, with someone asking follow-ups, makes those points second nature.

MockIF runs mock coding interviews with a voice AI interviewer in a real in-browser editor, in Python and TypeScript. It runs your code against tests, asks you to explain your approach, adds follow-up questions the way a real interviewer would, and then scores your answer and gives specific feedback. Each session costs 2 credits. It is free to start with 5 credits, then monthly or 3-monthly plans, or one-off credit packs (see pricing).

Frequently Asked Questions