Number of Islands BFS and DFS in DSA Typescript - Build from Scratch

Number of Islands BFS and DFS

📖 Scenario: Imagine you have a map represented as a grid. Each cell in the grid is either land ('1') or water ('0'). You want to find out how many separate islands are on the map. An island is a group of connected land cells horizontally or vertically.This is like counting how many separate patches of land you see when looking at a map from above.

🎯 Goal: You will build a program that counts the number of islands in a grid using two methods: Breadth-First Search (BFS) and Depth-First Search (DFS).This helps understand how to explore connected areas in grids, a common problem in maps, games, and image processing.

📋 What You'll Learn

Create a 2D array called grid with exact values representing land and water.

Create a variable called visited to track visited cells.

Implement BFS and DFS functions to explore connected land cells.

Count the number of islands using BFS and DFS separately.

Print the number of islands found by BFS and DFS.

💡 Why This Matters

🌍 Real World

Counting islands or connected regions is useful in map analysis, image processing, and game development where you need to find connected areas.

💼 Career

Understanding BFS and DFS for grid traversal is a common interview question and a fundamental skill for software engineers working with graphs and grids.

1

Create the grid map

Create a 2D array called grid with these exact values:
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']

DSA Typescript

# Create the 2D array grid with the given values
# Your code here

Hint

Use const grid: string[][] = [...] to create the 2D array with the exact rows.

2

Create the visited tracker

Create a 2D boolean array called visited with the same dimensions as grid, initialized with false for all cells.

DSA Typescript

const grid: string[][] = [
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
];
// Create visited array with false values
// Your code here

Hint

Use grid.map and inside it row.map(() => false) to create the visited array.

3

Implement BFS and DFS to count islands

Write two functions: bfs and dfs that take row and col as parameters and mark connected land cells as visited. Then write code to count islands by scanning grid and calling bfs and dfs respectively when an unvisited land cell is found. Store counts in bfsCount and dfsCount.

DSA Typescript

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

const visited: boolean[][] = grid.map(row => row.map(() => false));

// Write bfs and dfs functions and count islands
// Your code here

Hint

Use a queue for BFS and recursion for DFS. Mark visited cells to avoid counting the same island twice.

4

Print the number of islands found

Print the values of bfsCount and dfsCount using console.log with these exact messages:
"Number of islands (BFS): " + bfsCount
"Number of islands (DFS): " + dfsCount

DSA Typescript

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

const visited: boolean[][] = grid.map(row => row.map(() => false));

const rows = grid.length;
const cols = grid[0].length;

function bfs(row: number, col: number): void {
  const queue: [number, number][] = [];
  queue.push([row, col]);
  visited[row][col] = true;

  const directions = [[1,0], [-1,0], [0,1], [0,-1]];

  while(queue.length > 0) {
    const [r, c] = queue.shift()!;
    for (const [dr, dc] of directions) {
      const nr = r + dr;
      const nc = c + dc;
      if (nr >= 0 && nr = 0 && nc = rows || col = cols) return;
  if (visited[row][col]) return;
  if (grid[row][col] === '0') return;

  visited[row][col] = true;

  dfs(row + 1, col);
  dfs(row - 1, col);
  dfs(row, col + 1);
  dfs(row, col - 1);
}

// Count islands using BFS
let bfsCount = 0;
for (let r = 0; r < rows; r++) {
  for (let c = 0; c < cols; c++) {
    if (grid[r][c] === '1' && !visited[r][c]) {
      bfs(r, c);
      bfsCount++;
    }
  }
}

// Reset visited for DFS
for (let r = 0; r < rows; r++) {
  for (let c = 0; c < cols; c++) {
    visited[r][c] = false;
  }
}

// Count islands using DFS
let dfsCount = 0;
for (let r = 0; r < rows; r++) {
  for (let c = 0; c < cols; c++) {
    if (grid[r][c] === '1' && !visited[r][c]) {
      dfs(r, c);
      dfsCount++;
    }
  }
}

// Print the counts
// Your code here

Hint

Use console.log("Number of islands (BFS): " + bfsCount) and similarly for DFS.

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