Number of Islands BFS and DFS in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of the Number of Islands problem?

To count how many separate groups of connected '1's (land) exist in a 2D grid of '1's and '0's (land and water).

intermediate

How does Depth-First Search (DFS) help solve the Number of Islands problem?

DFS explores all connected land cells from a starting point by going deep into neighbors, marking them visited to avoid counting the same island multiple times.

intermediate

How does Breadth-First Search (BFS) differ from DFS in this problem?

BFS explores neighbors level by level using a queue, visiting all connected land cells around the starting point before moving deeper.

beginner

What data structure is commonly used to keep track of cells to visit in BFS for Number of Islands?

A queue is used to store cells to visit next in BFS, ensuring neighbors are processed in order of discovery.

beginner

Why do we mark cells as visited in Number of Islands algorithms?

Marking cells as visited prevents counting the same land cell multiple times and avoids infinite loops during traversal.

In the Number of Islands problem, what does a '1' represent in the grid?

A Obstacle

B Water

C Visited cell

D Land

'1' represents land cells where islands can form.

Which traversal method uses a stack or recursion to explore deep into neighbors?

A Depth-First Search (DFS)

B Breadth-First Search (BFS)

C Binary Search

D Linear Search

DFS uses recursion or a stack to explore neighbors deeply.

What data structure does BFS use to keep track of nodes to visit next?

A Stack

B Queue

C Set

D Tree

BFS uses a queue to process nodes in order of discovery.

Why do we mark cells as visited during traversal?

A To change their value to water

B To count them multiple times

C To avoid revisiting and infinite loops

D To sort the grid

Marking visited cells prevents revisiting and infinite loops.

If a grid has no '1's, what is the number of islands?

A 0

B 1

C Grid size

D Undefined

No land means zero islands.

Explain how DFS can be used to count the number of islands in a grid.

Think about exploring deep into connected land cells.

Describe the difference between BFS and DFS when solving the Number of Islands problem.

Focus on the order of visiting neighbors.

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