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.

Practice

1. What does the "Number of Islands" problem ask you to find in a grid of '1's and '0's?

easy

A. Calculate the perimeter of islands

B. Count how many groups of connected '1's (islands) exist

C. Count all '0's in the grid

D. Find the largest island size

Solution

1. Step 1: Understand the grid representation

   The grid contains '1's representing land and '0's representing water.

2. Step 2: Identify what the problem asks

   We need to count how many separate groups of connected '1's (islands) are present.

3. Final Answer:

   Count how many groups of connected '1's (islands) exist -> Option B

4. Quick Check:

   Islands = groups of connected '1's [OK]

Hint: Islands = connected lands, count groups of '1's [OK]

Common Mistakes:

• Counting total '1's instead of groups
• Confusing islands with largest island size
• Counting '0's instead of '1's

2. Which of the following TypeScript code snippets correctly initializes a 2D grid for the Number of Islands problem?

easy

A. const grid: string[] = ['10', '01'];

B. const grid: number[] = [1, 0, 0, 1];

C. const grid: string[][] = [['1','0'], ['0','1']];

D. const grid: string[][] = ['1', '0', '0', '1'];

Solution

1. Step 1: Check the grid type

   The grid should be a 2D array of strings representing '1' and '0'.

2. Step 2: Validate each option

   const grid: string[][] = [['1','0'], ['0','1']]; correctly uses a 2D array of strings. Others use incorrect types or structures.

3. Final Answer:

   const grid: string[][] = [['1','0'], ['0','1']]; -> Option C

4. Quick Check:

   2D array of strings = correct grid type [OK]

Hint: Grid must be 2D array of strings '1' or '0' [OK]

Common Mistakes:

• Using 1D arrays instead of 2D
• Using number arrays instead of string arrays
• Initializing grid as array of strings instead of array of arrays

3. Given the following grid, what is the number of islands found by a BFS or DFS algorithm?

const grid = [
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
];

medium

A. 4

B. 2

C. 1

D. 3

Solution

1. Step 1: Identify connected groups of '1's

   First island: top-left 2x2 block of '1's. Second island: single '1' at (2,2). Third island: two connected '1's at bottom-right.

2. Step 2: Count total islands

   There are 3 separate islands in total.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Count connected '1' groups = 3 [OK]

Hint: Count connected '1' clusters carefully [OK]

Common Mistakes:

• Counting diagonal connections as connected
• Missing single isolated '1's
• Counting all '1's instead of groups

4. Identify the bug in this DFS implementation for counting islands:

function dfs(grid: string[][], r: number, c: number) {
  if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] === '0') {
    return;
  }
  grid[r][c] = '0';
  dfs(grid, r + 1, c);
  dfs(grid, r - 1, c);
  dfs(grid, r, c + 1);
  // Missing dfs call here
}

medium

A. Missing dfs call for left neighbor (r, c - 1)

B. Should check for '1' instead of '0' in base case

C. grid[r][c] should be set to '1' instead of '0'

D. Parameters r and c are swapped in recursive calls

Solution

1. Step 1: Review recursive DFS calls

   DFS calls are made for down, up, and right neighbors but missing left neighbor (r, c - 1).

2. Step 2: Identify missing neighbor call

   Without calling dfs for left neighbor, some connected lands won't be visited, causing incorrect island count.

3. Final Answer:

   Missing dfs call for left neighbor (r, c - 1) -> Option A

4. Quick Check:

   All four directions must be checked [OK]

Hint: Check all 4 directions in DFS/BFS [OK]

Common Mistakes:

• Forgetting one direction in recursion
• Incorrect base case condition
• Not marking visited cells properly

5. You want to modify the BFS approach to count islands but only consider horizontal connections (left and right) and ignore vertical connections. Given this grid:

const grid = [
  ['1','0','1','0'],
  ['1','1','0','0'],
  ['0','0','1','1']
];

How many islands will your modified BFS count?

hard

A. 4

B. 3

C. 5

D. 6

Solution

1. Step 1: Understand horizontal-only connections

   Islands connect only left and right neighbors, vertical neighbors are ignored.

2. Step 2: Count islands with horizontal connections

   Row 0: '1' at (0,0) alone, '1' at (0,2) alone -> 2 islands.
   Row 1: '1's at (1,0) and (1,1) connected horizontally -> 1 island.
   Row 2: '1's at (2,2) and (2,3) connected horizontally -> 1 island.
   Total islands = 2 + 1 + 1 = 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Horizontal groups counted = 4 [OK]

Hint: Count only horizontal neighbors as connected [OK]

Common Mistakes:

• Counting vertical neighbors as connected
• Merging islands vertically by mistake
• Ignoring isolated horizontal '1's