Why Number of Islands BFS and DFS in DSA Typescript?

The Big Idea

Discover how simple searches can solve tricky island counting problems in seconds!

The Scenario

Imagine you have a big map made of squares, some are water and some are land. You want to count how many separate islands are on the map. Doing this by looking at each square and trying to remember which land belongs to which island by hand is very hard and confusing.

The Problem

Manually checking each square and trying to track connected lands is slow and easy to mess up. You might count the same island twice or miss some parts because it's hard to remember all connections without a clear method.

The Solution

Using BFS (Breadth-First Search) or DFS (Depth-First Search) helps you explore each island fully before moving to the next. These methods automatically find all connected land squares, so you count each island exactly once without confusion.

Before vs After

✗ Before

let count = 0;
for (let i = 0; i < rows; i++) {
  for (let j = 0; j < cols; j++) {
    if (grid[i][j] === '1') {
      count++;
      // Manually try to mark connected lands
    }
  }
}

✓ After

function bfs(grid, startRow, startCol) {
  let queue = [[startRow, startCol]];
  grid[startRow][startCol] = '0';
  while (queue.length > 0) {
    let [row, col] = queue.shift();
    let directions = [[1,0], [-1,0], [0,1], [0,-1]];
    for (let [dr, dc] of directions) {
      let r = row + dr, c = col + dc;
      if (r >= 0 && r < grid.length && c >= 0 && c < grid[0].length && grid[r][c] === '1') {
        queue.push([r, c]);
        grid[r][c] = '0';
      }
    }
  }
}

for (let i = 0; i < rows; i++) {
  for (let j = 0; j < cols; j++) {
    if (grid[i][j] === '1') {
      bfs(grid, i, j);
      count++;
    }
  }
}

What It Enables

This lets you quickly and correctly count all islands on any map, no matter how big or complex, without missing or double counting.

Real Life Example

Think about a drone flying over a flooded area. It needs to count how many separate dry land patches (islands) are left to plan rescue. BFS or DFS helps the drone's software do this fast and accurately.

Key Takeaways

Manually counting connected lands is confusing and error-prone.

BFS and DFS explore all connected parts of an island automatically.

This method ensures each island is counted once, making the task easy and reliable.

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