Number of Islands BFS and DFS in DSA Javascript - Execution Trace

Concept Flow - Number of Islands BFS and DFS

Start: Grid with 0s and 1s

↓

Scan each cell

↓

Is cell '1' and not visited?

No→Move to next cell

Yes↓

Increment island count

↓

Run BFS or DFS from this cell

↓

Mark all connected '1's as visited

↓

Continue scanning grid

↓

End: Return island count

Scan the grid cell by cell. When a '1' is found and not visited, start BFS or DFS to mark connected land. Count each such traversal as one island.

Execution Sample

DSA Javascript

function numIslands(grid) {
  let count = 0;
  const visited = new Set();
  const directions = [[1,0],[-1,0],[0,1],[0,-1]];
  function bfs(r, c) {
    const queue = [[r, c]];
    visited.add(`${r},${c}`);
    while (queue.length > 0) {
      const [row, col] = queue.shift();
      for (const [dr, dc] of directions) {
        const nr = row + dr, nc = col + dc;
        if (
          nr >= 0 && nr < grid.length &&
          nc >= 0 && nc < grid[0].length &&
          grid[nr][nc] === '1' &&
          !visited.has(`${nr},${nc}`)
        ) {
          visited.add(`${nr},${nc}`);
          queue.push([nr, nc]);
        }
      }
    }
  }
  for (let r = 0; r < grid.length; r++) {
    for (let c = 0; c < grid[0].length; c++) {
      if (grid[r][c] === '1' && !visited.has(`${r},${c}`)) {
        count++;
        bfs(r, c);
      }
    }
  }
  return count;
}

Counts islands by scanning grid and running BFS from each unvisited land cell.

Execution Table

Step	Operation	Current Cell	Visited Cells	Queue/Stack State	Island Count	Grid State (Visual)
1	Start scanning	None	{}	[]	0	[['1','1','0'],['0','1','0'],['0','0','1']]
2	Found '1' at (0,0)	(0,0)	{(0,0)}	[(0,0)]	1	[['1','1','0'],['0','1','0'],['0','0','1']]
3	BFS dequeue (0,0)	(0,0)	{(0,0)}	[]	1	[['1','1','0'],['0','1','0'],['0','0','1']]
4	Check neighbors of (0,0)	(0,0)	{(0,0),(0,1)}	[(0,1)]	1	[['1','1','0'],['0','1','0'],['0','0','1']]
5	BFS dequeue (0,1)	(0,1)	{(0,0),(0,1)}	[]	1	[['1','1','0'],['0','1','0'],['0','0','1']]
6	Check neighbors of (0,1)	(0,1)	{(0,0),(0,1),(1,1)}	[(1,1)]	1	[['1','1','0'],['0','1','0'],['0','0','1']]
7	BFS dequeue (1,1)	(1,1)	{(0,0),(0,1),(1,1)}	[]	1	[['1','1','0'],['0','1','0'],['0','0','1']]
8	Check neighbors of (1,1)	(1,1)	{(0,0),(0,1),(1,1)}	[]	1	[['1','1','0'],['0','1','0'],['0','0','1']]
9	Continue scanning	(1,2)	{(0,0),(0,1),(1,1)}	[]	1	[['1','1','0'],['0','1','0'],['0','0','1']]
10	Found '1' at (2,2)	(2,2)	{(0,0),(0,1),(1,1),(2,2)}	[(2,2)]	2	[['1','1','0'],['0','1','0'],['0','0','1']]
11	BFS dequeue (2,2)	(2,2)	{(0,0),(0,1),(1,1),(2,2)}	[]	2	[['1','1','0'],['0','1','0'],['0','0','1']]
12	Check neighbors of (2,2)	(2,2)	{(0,0),(0,1),(1,1),(2,2)}	[]	2	[['1','1','0'],['0','1','0'],['0','0','1']]
13	End scanning	None	{(0,0),(0,1),(1,1),(2,2)}	[]	2	[['1','1','0'],['0','1','0'],['0','0','1']]

💡 All cells scanned; BFS marked all connected lands; total islands counted.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 10	Final
count	0	1	1	1	2	2
visited	{}	{(0,0)}	{(0,0),(0,1)}	{(0,0),(0,1),(1,1)}	{(0,0),(0,1),(1,1),(2,2)}	{(0,0),(0,1),(1,1),(2,2)}
queue	[]	[(0,0)]	[(0,1)]	[(1,1)]	[(2,2)]	[]

Key Moments - 3 Insights

Why do we mark cells as visited during BFS/DFS?

Marking cells as visited prevents revisiting the same land cell multiple times, avoiding infinite loops and ensuring each island is counted once, as shown in steps 2-8 in the execution_table.

Why do we increment the island count only when we find an unvisited '1'?

Because each BFS/DFS from an unvisited '1' explores one whole island. Counting at discovery ensures each island is counted exactly once, as seen at step 2 and step 10.

What happens if we don't check neighbors correctly in BFS/DFS?

If neighbors are not checked or marked visited, connected land cells might be missed or counted multiple times, leading to wrong island counts. This is prevented by neighbor checks in steps 4, 6, and 8.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, which cells are visited?

A {(0,0),(0,1),(1,1)}

B {(0,0),(1,1)}

C {(0,1),(1,1)}

D {}

💡 Hint

Check the 'Visited Cells' column at step 6 in execution_table.

At which step does the island count increase to 2?

A Step 2

B Step 6

C Step 10

D Step 13

💡 Hint

Look at the 'Island Count' column in execution_table to find when count changes to 2.

If we skip marking visited cells, what will happen to the island count?

A It will be zero

B It may count the same island multiple times

C It will be correct

D It will count only water cells

💡 Hint

Refer to key_moments about why marking visited is important.

Concept Snapshot

Number of Islands BFS/DFS:
- Scan grid cell by cell
- When '1' found and unvisited, increment count
- Run BFS/DFS to mark connected land visited
- Continue until all cells checked
- Return total island count

Full Transcript

This visualization shows how to count islands in a grid using BFS or DFS. We scan each cell. When we find a '1' that is not visited, we increase the island count and run BFS or DFS to mark all connected land cells as visited. This prevents counting the same island multiple times. The execution table traces each step, showing the current cell, visited cells, queue or stack state, island count, and the grid state. Key moments clarify why marking visited is crucial and why counting happens only at discovery. The quiz tests understanding of visited cells, island count increments, and the importance of marking visited.

Practice

1. What does the "Number of Islands" problem ask you to find in a grid of '1's and '0's?

easy

A. Count how many groups of connected '1's (islands) are in the grid

B. Find the largest island size in the grid

C. Calculate the total number of '0's in the grid

D. Replace all '1's with '0's in the grid

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 an island means

   An island is a group of connected '1's horizontally or vertically.

3. Final Answer:

   Count how many groups of connected '1's (islands) are in the grid -> Option A

4. Quick Check:

   Number of islands = count of connected '1' groups [OK]

Hint: Islands = connected '1's groups, count them [OK]

Common Mistakes:

• Confusing island count with largest island size
• Counting '0's instead of '1's
• Ignoring connectivity rules (only horizontal/vertical)

2. Which of the following is the correct way to start a DFS function in JavaScript for the Number of Islands problem?

easy

A. function dfs(grid, r, c) { if (r < 0 || c < 0) return; }

B. function dfs(grid, r, c) { if (r <= 0 || c <= 0 || r > grid.length || c > grid[0].length) return; }

C. function dfs(grid, r, c) { if (r > grid.length || c > grid[0].length) return; }

D. function dfs(grid, r, c) { if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length) return; }

Solution

1. Step 1: Check boundary conditions for DFS

   We must stop DFS if row or column is outside grid bounds.

2. Step 2: Write correct boundary check

   Row or column less than 0 or greater or equal to grid size means out of bounds.

3. Final Answer:

   function dfs(grid, r, c) { if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length) return; } -> Option D

4. Quick Check:

   Boundary check includes all invalid indices [OK]

Hint: Check all out-of-bound indices with < 0 or >= length [OK]

Common Mistakes:

• Using > instead of >= for boundary check
• Missing some boundary conditions
• Using <= 0 which excludes valid index 0

3. What will be the output of the following code snippet for the grid below?

const grid = [ ['1','1','0','0'], ['1','0','0','1'], ['0','0','1','1'], ['0','0','0','0'] ]; function numIslands(grid) { let count = 0; const dfs = (r, c) => { if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || 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 < grid.length; r++) { for (let c = 0; c < grid[0].length; c++) { if (grid[r][c] === '1') { dfs(r, c); count++; } } } return count; } console.log(numIslands(grid));

medium

A. 1

B. 3

C. 2

D. 4

Solution

1. Step 1: Identify islands in the grid

   Islands are groups of connected '1's. Here, islands are: top-left (3 cells: (0,0),(0,1),(1,0)), single cell at (1,3), and bottom cluster (2 cells: (2,2),(2,3)). Total islands = 3.

2. Step 2: Count islands using DFS

   DFS marks visited '1's as '0'. After visiting each island, count increments. Total islands counted = 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Count connected '1' groups = 3 [OK]

Hint: Count connected '1' groups by marking visited [OK]

Common Mistakes:

• Counting diagonal connections as islands
• Not marking visited cells, causing overcount
• Misreading grid layout

4. The following BFS code for Number of Islands has a bug. What is the bug?

function bfs(grid, r, c) { const queue = [[r, c]]; while (queue.length > 0) { const [row, col] = queue.shift(); if (row < 0 || col < 0 || row >= grid.length || col >= grid[0].length || grid[row][col] === '0') continue; grid[row][col] = '0'; queue.push([row + 1, col]); queue.push([row - 1, col]); queue.push([row, col + 1]); queue.push([row, col - 1]); } }

medium

A. It does not check if a cell is already visited before pushing neighbors

B. It marks visited cells after adding neighbors to queue

C. It uses queue.shift() which is inefficient for large grids

D. It uses recursion instead of iteration

Solution

1. Step 1: Analyze neighbor addition in BFS

   The code adds neighbors to the queue without checking if they are visited or water.

2. Step 2: Identify consequence of missing check

   This causes multiple visits to the same cell, increasing runtime and possible infinite loops.

3. Final Answer:

   It does not check if a cell is already visited before pushing neighbors -> Option A

4. Quick Check:

   Check before enqueueing neighbors to avoid repeats [OK]

Hint: Check visited before enqueueing neighbors in BFS [OK]

Common Mistakes:

• Thinking queue.shift() inefficiency is the bug here
• Marking visited after enqueue instead of before
• Confusing recursion with iteration

5. Given a grid where diagonal connections also count as connected land, how would you modify the DFS to count islands correctly?

hard

A. Ignore diagonal neighbors and count only vertical connections

B. Only check horizontal neighbors (r,c+1) and (r,c-1)

C. Add diagonal neighbors (r+1,c+1), (r+1,c-1), (r-1,c+1), (r-1,c-1) to DFS calls

D. Use BFS instead of DFS without changing neighbors

Solution

1. Step 1: Understand connectivity rules

   Diagonal connections mean neighbors include diagonals, not just up/down/left/right.

2. Step 2: Modify DFS to include diagonal neighbors

   Add DFS calls for (r+1,c+1), (r+1,c-1), (r-1,c+1), (r-1,c-1) along with existing neighbors.

3. Final Answer:

   Add diagonal neighbors (r+1,c+1), (r+1,c-1), (r-1,c+1), (r-1,c-1) to DFS calls -> Option C

4. Quick Check:

   Include diagonal neighbors for diagonal connectivity [OK]

Hint: Add diagonal neighbors to DFS for diagonal island counting [OK]

Common Mistakes:

• Ignoring diagonal neighbors when required
• Switching BFS/DFS without changing neighbor logic
• Counting only horizontal or vertical neighbors