Number of Islands BFS and DFS in DSA Typescript

Mental Model

We find groups of connected land cells by exploring neighbors until no new land is found, counting each group as one island.

Analogy: Imagine walking through a forest and marking all trees connected by paths as one forest area before moving to the next unvisited tree group.

Grid example:
1 1 0 0 0
1 1 0 0 1
0 0 0 1 1
0 0 0 0 0
1 0 1 0 1

1 = land, 0 = water

Dry Run Walkthrough

Input: grid: [[1,1,0,0,0],[1,1,0,0,1],[0,0,0,1,1],[0,0,0,0,0],[1,0,1,0,1]]

Goal: Count how many separate islands (groups of connected 1s) are in the grid

Step 1: Start at (0,0), find land, begin BFS/DFS to mark connected land

Visited cells marked: (0,0), (0,1), (1,0), (1,1)
Grid with visited marked as X:
X X 0 0 0
X X 0 0 1
0 0 0 1 1
0 0 0 0 0
1 0 1 0 1

Why: We found the first island and mark all connected land to avoid recounting

Step 2: Move to (1,4), find new land, start BFS/DFS to mark connected land

Visited cells marked: (1,4), (2,3), (2,4)
Grid:
X X 0 0 0
X X 0 0 X
0 0 0 X X
0 0 0 0 0
1 0 1 0 1

Why: Second island found, mark all connected land

Step 3: Move to (4,0), find new land, mark it as visited

Visited cells marked: (4,0)
Grid:
X X 0 0 0
X X 0 0 X
0 0 0 X X
0 0 0 0 0
X 0 1 0 1

Why: Third island is a single cell

Step 4: Move to (4,2), find new land, mark it as visited

Visited cells marked: (4,2)
Grid:
X X 0 0 0
X X 0 0 X
0 0 0 X X
0 0 0 0 0
X 0 X 0 1

Why: Fourth island is a single cell

Step 5: Move to (4,4), find new land, mark it as visited

Visited cells marked: (4,4)
Grid:
X X 0 0 0
X X 0 0 X
0 0 0 X X
0 0 0 0 0
X 0 X 0 X

Why: Fifth island is a single cell

Result:

Final visited grid:
X X 0 0 0
X X 0 0 X
0 0 0 X X
0 0 0 0 0
X 0 X 0 X
Number of islands: 5

Annotated Code

DSA Typescript

class Solution {
  private rows: number;
  private cols: number;

  numIslands(grid: string[][]): number {
    if (grid.length === 0) return 0;
    this.rows = grid.length;
    this.cols = grid[0].length;
    let count = 0;

    for (let r = 0; r < this.rows; r++) {
      for (let c = 0; c < this.cols; c++) {
        if (grid[r][c] === '1') {
          count++;
          this.dfs(grid, r, c);
        }
      }
    }
    return count;
  }

  private dfs(grid: string[][], r: number, c: number): void {
    if (r < 0 || c < 0 || r >= this.rows || c >= this.cols || grid[r][c] === '0') {
      return;
    }
    grid[r][c] = '0'; // mark visited
    this.dfs(grid, r - 1, c); // up
    this.dfs(grid, r + 1, c); // down
    this.dfs(grid, r, c - 1); // left
    this.dfs(grid, r, c + 1); // right
  }
}

// Driver code
const grid = [
  ['1','1','0','0','0'],
  ['1','1','0','0','1'],
  ['0','0','0','1','1'],
  ['0','0','0','0','0'],
  ['1','0','1','0','1']
];
const solution = new Solution();
const result = solution.numIslands(grid);
console.log(result);

if (grid[r][c] === '1') {

Check if current cell is land to start island count and DFS

count++;

Increment island count for new island found

this.dfs(grid, r, c);

Start DFS to mark all connected land cells as visited

if (r < 0 || c < 0 || r >= this.rows || c >= this.cols || grid[r][c] === '0') { return; }

Stop DFS if out of bounds or water/visited cell

grid[r][c] = '0';

Mark current land cell as visited to avoid revisiting

this.dfs(grid, r - 1, c); this.dfs(grid, r + 1, c); this.dfs(grid, r, c - 1); this.dfs(grid, r, c + 1);

Recursively visit all four neighbors to cover entire island

Output

5

Complexity Analysis

Time: O(m*n) because each cell is visited once during DFS/BFS

Space: O(m*n) in worst case for recursion stack or queue when the grid is all land

vs Alternative: Compared to checking each cell multiple times, DFS/BFS marks visited cells to avoid repeated work, improving efficiency

Edge Cases

Empty grid

Returns 0 immediately as there are no islands

DSA Typescript

if (grid.length === 0) return 0;

Grid with all water (0s)

No islands found, returns 0

DSA Typescript

if (grid[r][c] === '1') {

Grid with all land (1s)

Counts as one big island, DFS/BFS visits all cells once

DSA Typescript

grid[r][c] = '0';

When to Use This Pattern

When you see a grid and need to find connected groups of cells, use DFS or BFS to explore neighbors and count distinct clusters.

Common Mistakes

Mistake: Not marking visited cells, causing infinite loops or overcounting islands
Fix: Mark cells as visited by changing their value or using a separate visited structure

Mistake: Checking only some neighbors and missing parts of islands
Fix: Always explore all four directions (up, down, left, right) for full coverage

Summary

Counts how many separate islands of connected land cells exist in a grid.

Use when you need to find connected groups in a 2D grid or matrix.

The key is to explore all connected neighbors from each unvisited land cell to mark entire islands.