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.

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