Number of Islands BFS and DFS in DSA Rust

Mental Model

We find groups of connected land cells by exploring neighbors until no new land is found, counting each group as one island.

Analogy: Imagine a map with patches of forest (land) separated by rivers (water). We walk through each forest patch fully before moving to the next, counting how many separate forests there are.

Grid example:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

1 = land, 0 = water

Dry Run Walkthrough

Input: grid: [[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]]

Goal: Count how many separate islands (connected groups of 1s) are in the grid

Step 1: Start at (0,0), find land, begin DFS/BFS to mark connected land

Visited (0,0), (0,1), (1,0), (1,1) marked as visited
Grid with visited marks:
[V V 0 0 0]
[V V 0 0 0]
[0 0 1 0 0]
[0 0 0 1 1]

Why: We explore all connected land from the first found cell to count one island

Step 2: Move to (0,1), already visited, skip

Same as previous

Why: Avoid counting the same island multiple times

Step 3: Move to (0,2), water, skip

Same as previous

Why: Water cells do not belong to any island

Step 4: Move to (2,2), find unvisited land, start DFS/BFS to mark connected land

Visited (2,2)
Grid:
[V V 0 0 0]
[V V 0 0 0]
[0 0 V 0 0]
[0 0 0 1 1]

Why: Found a new island, mark all connected land

Step 5: Move to (3,3), find unvisited land, start DFS/BFS to mark connected land

Visited (3,3), (3,4)
Grid:
[V V 0 0 0]
[V V 0 0 0]
[0 0 V 0 0]
[0 0 0 V V]

Why: Found another new island, mark all connected land

Step 6: All cells checked, total islands counted: 3

Final visited marks:
[V V 0 0 0]
[V V 0 0 0]
[0 0 V 0 0]
[0 0 0 V V]

Why: All islands found and counted

Result:

3 islands found
Grid with visited land marked as V:
[V V 0 0 0]
[V V 0 0 0]
[0 0 V 0 0]
[0 0 0 V V]

Annotated Code

DSA Rust

use std::collections::VecDeque;

fn num_islands_bfs(grid: &mut Vec<Vec<char>>) -> i32 {
    let rows = grid.len();
    if rows == 0 { return 0; }
    let cols = grid[0].len();
    let mut count = 0;

    for r in 0..rows {
        for c in 0..cols {
            if grid[r][c] == '1' {
                count += 1;
                let mut queue = VecDeque::new();
                queue.push_back((r, c));
                grid[r][c] = '0'; // mark visited

                while let Some((x, y)) = queue.pop_front() {
                    for (nx, ny) in [(x.wrapping_sub(1), y), (x+1, y), (x, y.wrapping_sub(1)), (x, y+1)] {
                        if nx < rows && ny < cols && grid[nx][ny] == '1' {
                            grid[nx][ny] = '0'; // mark visited
                            queue.push_back((nx, ny));
                        }
                    }
                }
            }
        }
    }
    count
}

fn num_islands_dfs(grid: &mut Vec<Vec<char>>) -> i32 {
    let rows = grid.len();
    if rows == 0 { return 0; }
    let cols = grid[0].len();
    let mut count = 0;

    fn dfs(grid: &mut Vec<Vec<char>>, r: usize, c: usize, rows: usize, cols: usize) {
        if r >= rows || c >= cols || grid[r][c] == '0' {
            return;
        }
        grid[r][c] = '0'; // mark visited
        if r > 0 { dfs(grid, r - 1, c, rows, cols); }
        if r + 1 < rows { dfs(grid, r + 1, c, rows, cols); }
        if c > 0 { dfs(grid, r, c - 1, rows, cols); }
        if c + 1 < cols { dfs(grid, r, c + 1, rows, cols); }
    }

    for r in 0..rows {
        for c in 0..cols {
            if grid[r][c] == '1' {
                count += 1;
                dfs(grid, r, c, rows, cols);
            }
        }
    }
    count
}

fn main() {
    let mut grid_bfs = vec![
        vec!['1','1','0','0','0'],
        vec!['1','1','0','0','0'],
        vec!['0','0','1','0','0'],
        vec!['0','0','0','1','1'],
    ];
    let mut grid_dfs = grid_bfs.clone();

    let count_bfs = num_islands_bfs(&mut grid_bfs);
    println!("Number of islands (BFS): {}", count_bfs);

    let count_dfs = num_islands_dfs(&mut grid_dfs);
    println!("Number of islands (DFS): {}", count_dfs);
}

if grid[r][c] == '1' {

Check if current cell is unvisited land to start island search

count += 1;

Increment island count when new land found

grid[r][c] = '0'; // mark visited

Mark current land cell as visited to avoid recounting

queue.push_back((r, c));

Add starting cell to BFS queue for exploration

while let Some((x, y)) = queue.pop_front() {

Process each cell in BFS queue to explore neighbors

if nx < rows && ny < cols && grid[nx][ny] == '1' {

Check if neighbor is valid and unvisited land

grid[nx][ny] = '0'; // mark visited

Mark neighbor as visited and add to queue

fn dfs(grid: &mut Vec<Vec<char>>, r: usize, c: usize, rows: usize, cols: usize) {

Recursive DFS to mark all connected land cells

if r >= rows || c >= cols || grid[r][c] == '0' { return; }

Stop DFS if out of bounds or water/visited

grid[r][c] = '0'; // mark visited

Mark current cell visited in DFS

dfs(grid, r - 1, c, rows, cols);

Explore upward neighbor

dfs(grid, r + 1, c, rows, cols);

Explore downward neighbor

dfs(grid, r, c - 1, rows, cols);

Explore left neighbor

dfs(grid, r, c + 1, rows, cols);

Explore right neighbor

Output

Number of islands (BFS): 3

Number of islands (DFS): 3

Complexity Analysis

Time: O(m*n) because each cell is visited once during BFS or DFS

Space: O(min(m,n)) for DFS recursion stack or BFS queue in worst case

vs Alternative: Naive approach checking neighbors repeatedly would be slower; BFS/DFS efficiently marks visited cells to avoid repeats

Edge Cases

Empty grid

Returns 0 islands immediately

DSA Rust

if rows == 0 { return 0; }

Grid with all water (0s)

No islands found, returns 0

DSA Rust

if grid[r][c] == '1' { ... }

Grid with one big island (all 1s)

Returns 1 after marking all connected land

DSA Rust

grid[r][c] = '0'; // mark visited

When to Use This Pattern

When you need to count connected groups in a grid, use BFS or DFS to explore neighbors and mark visited cells to avoid double counting.

Common Mistakes

Mistake: Not marking visited cells, causing infinite loops or overcounting
Fix: Mark cells as visited (e.g., change '1' to '0') immediately when discovered

Mistake: Checking neighbors without boundary checks, causing index errors
Fix: Always check if neighbor indices are within grid bounds before accessing

Summary

Counts how many separate islands (connected land groups) exist in a grid using BFS or DFS.

Use when you need to find connected components in a 2D grid or map.

The key insight is to explore all connected land from each unvisited land cell and mark them visited to avoid recounting.

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