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

Concept Flow - Number of Islands BFS and DFS

Start at first cell

↓

Is cell '1' and unvisited?

No→Move to next cell

|Yes↓

Increment island count

↓

Explore neighbors (BFS or DFS)

↓

Mark connected '1's as visited

↓

Continue scanning grid

↓

All cells checked?

No→Repeat

Yes↓

Return island count

Scan each cell; when a new island cell ('1') is found, explore all connected land cells using BFS or DFS to mark them visited, then continue scanning.

Execution Sample

DSA Rust

fn num_islands(grid: &mut Vec<Vec<char>>) -> i32 {
    let mut count = 0;
    for i in 0..grid.len() {
        for j in 0..grid[0].len() {
            if grid[i][j] == '1' {
                count += 1;
                dfs(grid, i, j);
            }
        }
    }
    count
}

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

Execution Table

Step	Operation	Cell Visited (i,j)	Island Count	Visited Cells Marked	Grid State (partial)
1	Check cell	(0,0)	0	None	[['1','1','0'], ['0','1','0'], ['0','0','1']]
2	Found '1', increment count	(0,0)	1	None	[['1','1','0'], ['0','1','0'], ['0','0','1']]
3	DFS start	(0,0)	1	(0,0)	[['V','1','0'], ['0','1','0'], ['0','0','1']]
4	DFS visit neighbor	(0,1)	1	(0,0),(0,1)	[['V','V','0'], ['0','1','0'], ['0','0','1']]
5	DFS visit neighbor	(1,1)	1	(0,0),(0,1),(1,1)	[['V','V','0'], ['0','V','0'], ['0','0','1']]
6	DFS ends	N/A	1	(0,0),(0,1),(1,1)	[['V','V','0'], ['0','V','0'], ['0','0','1']]
7	Check cell	(0,1)	1	(0,0),(0,1),(1,1)	[['V','V','0'], ['0','V','0'], ['0','0','1']]
8	Check cell	(0,2)	1	(0,0),(0,1),(1,1)	[['V','V','0'], ['0','V','0'], ['0','0','1']]
9	Check cell	(1,0)	1	(0,0),(0,1),(1,1)	[['V','V','0'], ['0','V','0'], ['0','0','1']]
10	Check cell	(1,1)	1	(0,0),(0,1),(1,1)	[['V','V','0'], ['0','V','0'], ['0','0','1']]
11	Check cell	(1,2)	1	(0,0),(0,1),(1,1)	[['V','V','0'], ['0','V','0'], ['0','0','1']]
12	Check cell	(2,0)	1	(0,0),(0,1),(1,1)	[['V','V','0'], ['0','V','0'], ['0','0','1']]
13	Check cell	(2,1)	1	(0,0),(0,1),(1,1)	[['V','V','0'], ['0','V','0'], ['0','0','1']]
14	Check cell	(2,2)	1	(0,0),(0,1),(1,1)	[['V','V','0'], ['0','V','0'], ['0','0','1']]
15	Found '1', increment count	(2,2)	2	(0,0),(0,1),(1,1)	[['V','V','0'], ['0','V','0'], ['0','0','1']]
16	DFS start	(2,2)	2	(0,0),(0,1),(1,1),(2,2)	[['V','V','0'], ['0','V','0'], ['0','0','V']]
17	DFS ends	N/A	2	(0,0),(0,1),(1,1),(2,2)	[['V','V','0'], ['0','V','0'], ['0','0','V']]
18	Check cell	(2,2)	2	(0,0),(0,1),(1,1),(2,2)	[['V','V','0'], ['0','V','0'], ['0','0','V']]
19	All cells checked	N/A	2	(0,0),(0,1),(1,1),(2,2)	[['V','V','0'], ['0','V','0'], ['0','0','V']]

💡 All cells checked, total islands counted = 2

Variable Tracker

Variable	Start	After Step 2	After Step 6	After Step 15	After Step 17	Final
count	0	1	1	2	2	2
visited cells	{}	{(0,0)}	{(0,0),(0,1),(1,1)}	{(0,0),(0,1),(1,1)}	{(0,0),(0,1),(1,1),(2,2)}	{(0,0),(0,1),(1,1),(2,2)}

Key Moments - 3 Insights

Why do we mark cells as visited during DFS?

Marking cells as visited prevents revisiting the same land cell multiple times, avoiding infinite loops and double counting. See steps 3-6 in execution_table where connected cells are marked.

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

Each unvisited '1' represents a new island. Connected '1's are part of the same island and marked visited during DFS. This is shown at steps 2 and 15 where count increments only on new island discovery.

What happens if the grid has no '1's?

The count remains zero because no DFS is triggered. The loops scan all cells but never find '1'. This is implied by the absence of increment steps in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, what is the island count after step 6?

A 1

B 0

C 2

D 3

💡 Hint

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

At which step does the algorithm find the second island?

A Step 10

B Step 15

C Step 12

D Step 18

💡 Hint

Look for the step where 'Found '1', increment count' happens second time in execution_table.

If we did not mark visited cells, what would happen during DFS?

A Algorithm would count islands correctly

B Algorithm would skip some islands

C Algorithm could enter infinite loops revisiting cells

D Algorithm would run faster

💡 Hint

Refer to key_moments about marking visited cells to avoid revisiting.

Concept Snapshot

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

Full Transcript

The Number of Islands problem counts groups of connected '1's in a grid. We scan each cell. When we find a '1' that is not visited, we increase the island count and explore all connected land cells using DFS or BFS to mark them 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, islands counted, and visited cells marked. Key moments clarify why marking visited cells is important and when the count increments. The visual quiz tests understanding of island count at specific steps and the role of visited marking.

Practice

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

easy

A. Find the largest island size in the grid

B. Count how many '0's are in the grid

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

D. Calculate the perimeter of all islands combined

Solution

1. Step 1: Understand the grid content

   The grid contains '1's representing land and '0's representing water.

2. Step 2: Define the problem goal

   The problem asks to count how many separate groups of connected '1's exist, called islands.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Confusing island count with largest island size
• Counting '0's instead of '1's
• Calculating perimeter instead of count

2. Which Rust code snippet correctly initializes a 2D vector grid of chars for the Number of Islands problem?

easy

A. let grid: Vec<char> = vec!['1', '0', '0', '1'];

B. let grid: Vec = vec![vec!['1', '0'], vec!['0', '1']];

C. let grid: Vec = vec![vec![1, 0], vec![0, 1]];

D. let grid = [[1, 0], [0, 1]];

Solution

1. Step 1: Identify correct data type for grid

   The grid should be a 2D vector of chars because the problem uses '1' and '0' as characters.

2. Step 2: Check syntax for 2D vector initialization

   let grid: Vec = vec![vec!['1', '0'], vec!['0', '1']]; uses Vec with vec! macro and char literals '1' and '0', which is correct Rust syntax.

3. Final Answer:

   let grid: Vec = vec![vec!['1', '0'], vec!['0', '1']]; -> Option B

4. Quick Check:

   2D vector of chars with vec! and '1'/'0' chars [OK]

Hint: Use Vec with vec![vec!['1', '0'], ...] [OK]

Common Mistakes:

• Using integer types instead of char
• Using arrays without specifying type
• Using 1D vector instead of 2D

3. Given the following Rust code using DFS to count islands, what is the output?

fn main() {
    let mut grid = vec![
        vec!['1', '1', '0', '0'],
        vec!['1', '0', '0', '1'],
        vec!['0', '0', '1', '1'],
        vec!['0', '0', '0', '0'],
    ];
    println!("{}", num_islands(&mut grid));
}

fn num_islands(grid: &mut Vec) -> i32 {
    let mut count = 0;
    for i in 0..grid.len() {
        for j in 0..grid[0].len() {
            if grid[i][j] == '1' {
                dfs(grid, i, j);
                count += 1;
            }
        }
    }
    count
}

fn dfs(grid: &mut Vec, i: usize, j: usize) {
    if i >= grid.len() || j >= grid[0].len() || grid[i][j] == '0' {
        return;
    }
    grid[i][j] = '0';
    if i > 0 { dfs(grid, i - 1, j); }
    dfs(grid, i + 1, j);
    if j > 0 { dfs(grid, i, j - 1); }
    dfs(grid, i, j + 1);
}

medium

A. 5

B. 4

C. 2

D. 3

Solution

1. Step 1: Identify islands in the grid

   The grid has these islands: - Top-left corner: (0,0),(0,1),(1,0) - Single '1' at (1,3) - Connected '1's at (2,2),(2,3)

2. Step 2: Count islands after DFS marks visited

   DFS marks connected '1's as '0' to avoid recounting. Total islands found = 3.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Count connected groups = 3 [OK]

Hint: Count connected '1' groups, DFS marks visited [OK]

Common Mistakes:

• Counting diagonal connections as islands
• Not marking visited cells
• Off-by-one errors in loops

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

fn dfs(grid: &mut Vec, i: usize, j: usize) {
    if i > grid.len() || j > grid[0].len() || grid[i][j] == '0' {
        return;
    }
    grid[i][j] = '0';
    if i > 0 { dfs(grid, i - 1, j); }
    dfs(grid, i + 1, j);
    if j > 0 { dfs(grid, i, j - 1); }
    dfs(grid, i, j + 1);
}

medium

A. The boundary check uses '>' instead of '>=' causing out-of-bounds panic

B. The grid is not marked visited correctly

C. The DFS does not check for diagonal neighbors

D. The function does not return the island count

Solution

1. Step 1: Analyze boundary condition in DFS

   The code checks if i > grid.len() or j > grid[0].len(), but valid indices go up to len()-1, so i == len() is out-of-bounds.

2. Step 2: Correct boundary check to prevent panic

   Use i >= grid.len() and j >= grid[0].len() to avoid accessing invalid indices and crashing.

3. Final Answer:

   The boundary check uses '>' instead of '>=' causing out-of-bounds panic -> Option A

4. Quick Check:

   Use >= for boundary checks to avoid panic [OK]

Hint: Use >= for boundary checks to avoid index errors [OK]

Common Mistakes:

• Using > instead of >= in boundary checks
• Forgetting to mark visited cells
• Ignoring out-of-bounds errors

5. You want to modify the Number of Islands BFS solution to also return the size of the largest island. Which change is correct?

hard

A. Add a counter inside BFS to count connected '1's and track max size

B. Count '1's in the grid before BFS and return that count

C. Use DFS instead of BFS without any modification

D. Return the total number of '0's as the largest island size

Solution

1. Step 1: Understand BFS traversal for islands

   BFS visits all connected '1's in an island. Counting visited nodes during BFS gives island size.

2. Step 2: Track and update largest island size

   Maintain a counter inside BFS for current island size, update max size after BFS completes for each island.

3. Final Answer:

   Add a counter inside BFS to count connected '1's and track max size -> Option A

4. Quick Check:

   Count nodes during BFS to find largest island size [OK]

Hint: Count nodes during BFS, update max size [OK]

Common Mistakes:

• Counting '1's before BFS (not island size)
• Using DFS without counting size
• Returning count of '0's instead of island size