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.