Number of Islands BFS and DFS in DSA C++ - 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 to mark connected 1s as visited

↓

Mark all connected land cells

↓

Continue scanning grid

↓

All cells scanned?

No→Repeat scan

Yes↓

Return total island count

Scan the grid cell by cell; when a land cell (1) not visited is found, increase island count and use BFS or DFS to mark all connected land cells as visited, then continue scanning.

Execution Sample

DSA C++

void dfs(vector<vector<char>>& grid, int i, int j) {
  if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] != '1')
    return;
  grid[i][j] = 'V';
  dfs(grid, i + 1, j);
  dfs(grid, i - 1, j);
  dfs(grid, i, j + 1);
  dfs(grid, i, j - 1);
}

int numIslands(vector<vector<char>>& grid) {
  int count = 0;
  for (int i = 0; i < grid.size(); i++) {
    for (int j = 0; j < grid[0].size(); j++) {
      if (grid[i][j] == '1') {
        count++;
        dfs(grid, i, j);
      }
    }
  }
  return count;
}

Counts islands by scanning grid and calling DFS to mark connected land cells.

Execution Table

Step	Operation	Current Cell (i,j)	Island Count	Visited Cells Marked	Grid Visual State
1	Start scanning grid	-	0	None	[ ['1','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1'] ]
2	Found land cell	(0,0)	1	(0,0)	[ ['V','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1'] ]
3	DFS marks connected land	(0,1)	1	(0,1)	[ ['V','V','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1'] ]
4	DFS marks connected land	(1,0)	1	(1,0)	[ ['V','V','0','0','0'], ['V','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1'] ]
5	DFS marks connected land	(1,1)	1	(1,1)	[ ['V','V','0','0','0'], ['V','V','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1'] ]
6	Continue scanning	(0,2)	1	No change	[ ['V','V','0','0','0'], ['V','V','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1'] ]
7	Found land cell	(2,2)	2	(2,2)	[ ['V','V','0','0','0'], ['V','V','0','0','0'], ['0','0','V','0','0'], ['0','0','0','1','1'] ]
8	DFS marks connected land	(2,2)	2	(2,2)	[ ['V','V','0','0','0'], ['V','V','0','0','0'], ['0','0','V','0','0'], ['0','0','0','1','1'] ]
9	Continue scanning	(3,3)	2	No change	[ ['V','V','0','0','0'], ['V','V','0','0','0'], ['0','0','V','0','0'], ['0','0','0','1','1'] ]
10	Found land cell	(3,3)	3	(3,3)	[ ['V','V','0','0','0'], ['V','V','0','0','0'], ['0','0','V','0','0'], ['0','0','0','V','1'] ]
11	DFS marks connected land	(3,4)	3	(3,4)	[ ['V','V','0','0','0'], ['V','V','0','0','0'], ['0','0','V','0','0'], ['0','0','0','V','V'] ]
12	Finish scanning all cells	-	3	All connected lands visited	[ ['V','V','0','0','0'], ['V','V','0','0','0'], ['0','0','V','0','0'], ['0','0','0','V','V'] ]

💡 All cells scanned; all islands counted and connected lands marked visited.

Variable Tracker

Variable	Start	After Step 2	After Step 7	After Step 10	Final
Island Count	0	1	2	3	3
Visited Cells	None	(0,0),(0,1),(1,0),(1,1)	(0,0),(0,1),(1,0),(1,1),(2,2)	(0,0),(0,1),(1,0),(1,1),(2,2),(3,3),(3,4)	(0,0),(0,1),(1,0),(1,1),(2,2),(3,3),(3,4)

Key Moments - 3 Insights

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

Marking connected land cells as visited prevents counting the same island multiple times, as shown in steps 2 to 5 where all connected '1's are marked 'V'.

What happens if we don't check if a cell is already visited before DFS/BFS?

Without checking visited cells, DFS/BFS would revisit cells endlessly or count the same island multiple times, causing incorrect island count, as seen in the scanning steps.

Why do we increment island count only when we find an unvisited land cell?

Because each unvisited land cell found starts a new island exploration, incrementing count only then avoids double counting connected lands, as shown in steps 2, 7, and 10.

Visual Quiz - 3 Questions

Look at the execution table, what is the island count after step 7?

A 1

B 3

C 2

D 0

💡 Hint

Check the 'Island Count' column at step 7 in the execution_table.

At which step are the cells (3,3) and (3,4) marked visited?

A Step 7

B Step 10 and 11

C Step 2 and 3

D Step 5

💡 Hint

Look at the 'Visited Cells Marked' and 'Grid Visual State' columns for steps 10 and 11.

If the grid had no '1's, what would the island count be after scanning?

A 0

B 1

C Number of cells

D Undefined

💡 Hint

Refer to the initial 'Island Count' at start and the condition for incrementing count in the execution_table.

Concept Snapshot

Number of Islands BFS and DFS:
- Scan each cell in grid
- If cell is '1' and not visited, increment island count
- Use DFS or BFS to mark all connected '1's as visited
- Continue until all cells scanned
- Return total island count

Full Transcript

This concept counts the number of islands in a grid of '1's and '0's. We scan each cell. When we find a '1' that is not visited, we increase the island count and run DFS or BFS to mark all connected land cells as visited. This prevents counting the same island multiple times. We continue scanning until all cells are checked. The final count is the number of islands. The execution table shows step-by-step how cells are visited and islands counted. Key moments clarify why marking visited cells is important and when to increment the count.

Practice

1. What does the "Number of Islands" problem ask you to find in a 2D grid of '1's (land) and '0's (water)?

easy

A. Count total number of '1's in the grid

B. Count how many separate groups of connected '1's exist

C. Find the largest island size

D. Find the shortest path between two islands

Solution

1. Step 1: Understand the problem definition

   The problem asks to count distinct islands, where an island is a group of connected '1's horizontally or vertically.

2. Step 2: Clarify what is being counted

   We count how many separate clusters of '1's exist, not the total number of '1's or sizes.

3. Final Answer:

   Count how many separate groups of connected '1's exist -> Option B

4. Quick Check:

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

Hint: Islands = groups of connected '1's, count groups not cells [OK]

Common Mistakes:

• Counting total '1's instead of groups
• Including diagonal connections as connected
• Confusing island size with island count

2. Which of the following C++ code snippets correctly initializes a 2D vector grid of chars with given rows and columns filled with '0'?

easy

A. std::vector grid(rows, std::vector<char>(cols, '0'));

B. std::vector<char> grid(rows, std::vector<char>(cols, '0'));

C. std::vector grid(cols, std::vector<char>(rows, '0'));

D. std::vector grid(rows, cols, '0');

Solution

1. Step 1: Understand 2D vector initialization syntax

   To create a 2D vector of chars, use vector of vectors: outer vector size = rows, inner vector size = cols.

2. Step 2: Check each option

   std::vector grid(rows, std::vector<char>(cols, '0')); correctly creates 'rows' vectors each with 'cols' chars initialized to '0'. Others have wrong types or parameters.

3. Final Answer:

   std::vector grid(rows, std::vector<char>(cols, '0')); -> Option A

4. Quick Check:

   2D vector init = vector of vectors with sizes [OK]

Hint: Use vector(rows, vector<char>(cols, '0')) [OK]

Common Mistakes:

• Swapping rows and cols sizes
• Using wrong vector types
• Trying to initialize 2D vector with three parameters

3. Given the following grid and BFS-based code snippet to count islands, what is the output?

std::vector grid = {
  {'1','1','0','0'},
  {'1','0','0','1'},
  {'0','0','1','1'},
  {'0','0','0','0'}
};
int countIslands(const std::vector& grid) {
  int count = 0;
  int rows = grid.size();
  int cols = grid[0].size();
  std::vector visited(rows, std::vector<bool>(cols, false));
  std::queue> q;
  int directions[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
  for(int i=0; i=0 && nr=0 && nc

medium

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Identify islands in the grid

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

2. Step 2: Understand BFS traversal

   The BFS marks all connected '1's visited per island, so count increments once per island found.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Count islands = 3 [OK]

Hint: Count connected groups by BFS marking visited [OK]

Common Mistakes:

• Counting diagonal connections as islands
• Missing isolated '1's as separate islands
• Not marking visited correctly causing overcount

4. The following DFS code for counting islands has a bug. What is the bug?

void dfs(int r, int c, std::vector& grid) {
  int rows = grid.size();
  int cols = grid[0].size();
  if(r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] == '0')
    return;
  grid[r][c] = '0';
  dfs(r+1, c, grid);
  dfs(r-1, c, grid);
  dfs(r, c+1, grid);
  dfs(r, c-1, grid);
}

int numIslands(std::vector& grid) {
  int count = 0;
  for(int i=0; i

medium

A. The base case does not check for visited cells

B. The DFS does not check boundaries correctly

C. The DFS does not mark visited cells, causing infinite recursion

D. The grid is modified during DFS, which is incorrect

Solution

1. Step 1: Analyze DFS grid modification

   The DFS marks visited cells by changing '1' to '0' in the original grid, modifying input.

2. Step 2: Identify why this is a bug

   Modifying input grid may be unintended side effect; better to use a separate visited array to avoid altering input data.

3. Final Answer:

   The grid is modified during DFS, which is incorrect -> Option D

4. Quick Check:

   Modifying input grid = bug [OK]

Hint: Avoid changing input grid; use visited array instead [OK]

Common Mistakes:

• Ignoring that grid is changed in-place
• Assuming no visited tracking needed
• Misreading boundary checks as incorrect

5. You want to count islands in a grid where diagonal connections also count as connected (8 directions). How should you modify the BFS or DFS approach?

hard

A. Count islands by summing all '1's without traversal

B. Only check horizontal neighbors, ignore vertical and diagonal

C. Add diagonal directions (like (1,1), (1,-1), (-1,1), (-1,-1)) to the directions array

D. Use BFS for horizontal and DFS for vertical connections separately

Solution

1. Step 1: Understand connectivity change

   Diagonal connections mean neighbors include 8 directions: up, down, left, right, and 4 diagonals.

2. Step 2: Modify directions array

   Add diagonal moves (1,1), (1,-1), (-1,1), (-1,-1) to directions used in BFS or DFS to explore all connected neighbors.

3. Final Answer:

   Add diagonal directions (like (1,1), (1,-1), (-1,1), (-1,-1)) to the directions array -> Option C

4. Quick Check:

   Include all 8 neighbors for diagonal connectivity [OK]

Hint: Add diagonal moves to directions for 8-way connectivity [OK]

Common Mistakes:

• Ignoring diagonal neighbors
• Counting only horizontal or vertical neighbors
• Trying to count without traversal