Number of Islands BFS and DFS in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BFS traversal on grid

What is the number of islands found by BFS in the given grid?

DSA Typescript

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

function numIslandsBFS(grid: string[][]): number {
  if (!grid.length) return 0;
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;
  const directions = [[1,0],[-1,0],[0,1],[0,-1]];

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count++;
        const queue = [[r,c]];
        grid[r][c] = '0';
        while(queue.length) {
          const [x,y] = queue.shift()!;
          for (const [dx,dy] of directions) {
            const nx = x + dx;
            const ny = y + dy;
            if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] === '1') {
              queue.push([nx, ny]);
              grid[nx][ny] = '0';
            }
          }
        }
      }
    }
  }
  return count;
}

console.log(numIslandsBFS(grid));

A 1

B 2

C 4

D 3

💡 Hint

Count connected groups of '1's using BFS.

The BFS visits each island once and marks visited cells. There are three islands in the grid.

❓ Predict Output

intermediate

Output of DFS traversal on grid

What is the number of islands found by DFS in the given grid?

DSA Typescript

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

function numIslandsDFS(grid: string[][]): number {
  if (!grid.length) return 0;
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;

  function dfs(r: number, c: number) {
    if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] === '0') return;
    grid[r][c] = '0';
    dfs(r+1, c);
    dfs(r-1, c);
    dfs(r, c+1);
    dfs(r, c-1);
  }

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

console.log(numIslandsDFS(grid));

A 1

B 3

C 2

D 4

💡 Hint

Use DFS to mark all connected land cells.

DFS explores all connected land cells recursively. The grid has three islands.

🧠 Conceptual

advanced

Why mark visited cells in Number of Islands?

Why do BFS and DFS algorithms mark visited land cells as '0' or visited when counting islands?

A To avoid counting the same island multiple times by revisiting cells.

B To increase the number of islands found by splitting them.

C To convert water cells into land cells for easier traversal.

D To speed up the algorithm by skipping water cells.

💡 Hint

Think about what happens if you revisit the same land cell.

Marking visited cells prevents revisiting and recounting the same island multiple times.

❓ Predict Output

advanced

Output after modifying grid during DFS

What is the final state of the grid after running DFS-based number of islands on this input?

DSA Typescript

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

function numIslandsDFS(grid: string[][]): number {
  if (!grid.length) return 0;
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;

  function dfs(r: number, c: number) {
    if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] === '0') return;
    grid[r][c] = '0';
    dfs(r+1, c);
    dfs(r-1, c);
    dfs(r, c+1);
    dfs(r, c-1);
  }

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

numIslandsDFS(grid);
console.log(grid);

A [['0','0','1'],['0','0','0'],['1','0','0']]

B [['1','0','1'],['0','1','0'],['1','0','1']]

C [['0','0','0'],['0','0','0'],['0','0','0']]

D [['0','0','0'],['0','1','0'],['0','0','0']]

💡 Hint

DFS changes all connected '1's to '0's.

DFS visits each island cell and marks it '0'. All islands are single cells here, so all become '0'.

🧠 Conceptual

expert

Time complexity of Number of Islands algorithms

What is the time complexity of BFS or DFS approach to count the number of islands in an m x n grid?

A O(m * n), because each cell is visited at most once.

B O(m + n), because BFS/DFS only traverse rows and columns separately.

C O((m * n)^2), because each cell is compared with every other cell.

D O(1), because the grid size is fixed.

💡 Hint

Consider how many times each cell is processed.

Each cell is visited once during BFS or DFS, so complexity is proportional to total cells.