Number of Islands BFS and DFS in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to start BFS from the given cell.

DSA Typescript

queue.push([row, [1]]);

Drag options to blanks, or click blank then click option'

Acol

Brow

Cgrid

Dvisited

Attempts:

3 left

💡 Hint

Common Mistakes

Pushing only the row index.

Pushing the grid or visited array instead of column.

We push the current cell's column index along with the row to the queue to start BFS.

2fill in blank

medium

Complete the code to mark the current cell as visited.

DSA Typescript

visited[[1]][col] = true;

Drag options to blanks, or click blank then click option'

Arow

Bcol

Cgrid

Dqueue

Attempts:

3 left

💡 Hint

Common Mistakes

Marking visited using column index only.

Marking grid or queue instead of visited.

We mark the current row and column as visited to avoid revisiting.

3fill in blank

hard

Fix the error in the DFS recursive call to explore neighbors.

DSA Typescript

dfs(grid, row + [1], col + [2], visited);

Drag options to blanks, or click blank then click option'

A1

B0

C-1

Drow

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 for both row and column changes (no movement).

Using row variable instead of numeric offsets.

To explore neighbors, we add or subtract 1 from row or column. Here, row is decreased by 1 and column stays the same.

4fill in blank

hard

Fill both blanks to check if the neighbor cell is valid and unvisited.

DSA Typescript

if (row + [1] >= 0 && row + [1] < grid.length && col + [2] >= 0 && col + [2] < grid[0].length && !visited[row + [1]][col + [2]] && grid[row + [1]][col + [2]] === '1') {

Drag options to blanks, or click blank then click option'

Adr

Bdc

C-1

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using fixed numbers instead of direction variables.

Not checking boundaries properly.

We use dr and dc as row and column direction offsets to check neighbors.

5fill in blank

hard

Fill all three blanks to create a loop over all four directions for BFS.

DSA Typescript

const directions = [[[1], 0], [[2], 0], [0, [3]], [0, -[3]]];

Drag options to blanks, or click blank then click option'

A1

B-1

D2

Attempts:

3 left

💡 Hint

Common Mistakes

Using 2 instead of 1 for direction offsets.

Mixing up positive and negative signs.

Directions represent up (1,0), down (-1,0), right (0,1), left (0,-1) moves.

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