Number of Islands BFS and DFS in DSA Rust - Deep Dive

Overview - Number of Islands BFS and DFS

What is it?

Number of Islands is a problem where you count how many separate groups of connected 'land' cells exist in a grid. Each cell can be water or land, and connected land cells form an island. We use BFS (Breadth-First Search) or DFS (Depth-First Search) to explore and mark these islands. This helps us find how many islands are in the grid.

Why it matters

Without this method, it would be hard to find connected groups in grids, which is important in maps, games, and image processing. It helps computers understand shapes and clusters in data. Without it, many applications like flood fill, network grouping, or pathfinding would be inefficient or impossible.

Where it fits

You should know basic arrays and grids before this. After this, you can learn graph traversal algorithms, connected components, and more complex grid problems like shortest path or maze solving.

Mental Model

Core Idea

Explore each land cell and mark all connected land cells as one island using BFS or DFS to count distinct islands.

Think of it like...

Imagine walking on a map where land patches are islands. When you step on land, you explore all connected land around you before moving on, so you count one island at a time.

Grid example:

  1 1 0 0 0
  1 1 0 0 1
  0 0 0 1 1
  0 0 0 0 0
  1 0 1 0 1

Islands found:
  Island 1: top-left cluster (cells with 1s connected)
  Island 2: middle-right cluster
  Island 3: bottom-left single cell
  Island 4: bottom-middle single cell
  Island 5: bottom-right single cell

Build-Up - 7 Steps

1

Foundation

Understanding the Grid and Islands

Concept: Introduce the grid structure and what counts as an island.

A grid is a 2D array where each cell is either '1' (land) or '0' (water). An island is a group of '1's connected horizontally or vertically (not diagonally). We want to count how many such groups exist.

Result

You can identify land and water cells and understand what an island looks like in the grid.

Understanding the grid and island definition is the base for any traversal or counting method.

2

Foundation

Basic Depth-First Search (DFS) Exploration

Concept: Use DFS to explore connected land cells starting from one cell.

Starting from a land cell, recursively visit all adjacent land cells (up, down, left, right). Mark visited cells to avoid counting them again. This explores one island fully.

Result

You can explore and mark all cells of one island starting from any land cell.

Knowing how to explore connected cells fully is key to counting islands correctly.

3

Intermediate

Counting Islands Using DFS

🤔Before reading on: do you think counting islands requires exploring every cell or just land cells? Commit to your answer.

Concept: Combine DFS exploration with a loop over the grid to count all islands.

Loop over each cell in the grid. When you find a land cell not visited before, start DFS from it to mark the whole island. Increase island count by one. Continue until all cells are checked.

Result

You get the total number of islands in the grid.

Understanding that each DFS call corresponds to one island helps you count islands efficiently without double counting.

4

Intermediate

Breadth-First Search (BFS) Alternative

🤔Before reading on: do you think BFS and DFS will find different numbers of islands? Commit to your answer.

Concept: Use BFS instead of DFS to explore islands, showing an alternative traversal method.

Starting from a land cell, use a queue to visit all connected land cells level by level. Mark visited cells. This also explores one island fully. Use BFS in the same counting loop.

Result

BFS also counts the same number of islands as DFS.

Knowing BFS is an alternative to DFS shows flexibility in traversal methods and helps understand their differences and similarities.

5

Intermediate

Handling Edge Cases and Grid Boundaries

🤔Before reading on: do you think checking neighbors outside the grid is safe? Commit to your answer.

Concept: Learn to safely check neighbors without going outside grid boundaries.

When exploring neighbors (up, down, left, right), always check if the neighbor's row and column are within grid limits before accessing. This prevents errors.

Result

Traversal works correctly without runtime errors or wrong counts.

Understanding boundary checks prevents common bugs and ensures robust traversal.

6

Advanced

Optimizing Space with In-Place Marking

🤔Before reading on: do you think using extra memory for visited cells is always necessary? Commit to your answer.

Concept: Mark visited land cells directly in the grid to save extra space.

Instead of using a separate visited array, change visited land cells from '1' to '0' during traversal. This marks them as water, so they won't be revisited.

Result

Memory usage is reduced, and the algorithm still counts islands correctly.

Knowing in-place marking reduces memory overhead and simplifies code in many grid problems.

7

Expert

Comparing BFS and DFS Performance and Use Cases

🤔Before reading on: do you think BFS is always faster than DFS or vice versa? Commit to your answer.

Concept: Understand the tradeoffs between BFS and DFS in this problem.

DFS uses recursion or a stack and can be faster in practice due to less overhead. BFS uses a queue and explores neighbors level-wise, which can be useful if shortest path info is needed. Both have similar time complexity O(m*n).

Result

You can choose BFS or DFS based on problem needs and environment constraints.

Knowing the strengths and weaknesses of BFS and DFS helps pick the right tool for different grid problems beyond counting islands.

Under the Hood

The grid is treated like a graph where each cell is a node connected to up to four neighbors. BFS and DFS traverse this graph by visiting nodes and marking them visited to avoid repeats. DFS uses a call stack or explicit stack to go deep before backtracking, while BFS uses a queue to explore neighbors level by level. Marking visited nodes prevents infinite loops and double counting.

Why designed this way?

This approach leverages classic graph traversal algorithms adapted to grids, which are simpler to implement and understand. Alternatives like Union-Find exist but are more complex. BFS and DFS are intuitive and efficient for this problem, making them the standard solution.

Grid as graph:

┌───┬───┬───┐
│ 1 │ 1 │ 0 │
├───┼───┼───┤
│ 1 │ 0 │ 1 │
├───┼───┼───┤
│ 0 │ 1 │ 1 │
└───┴───┴───┘

Connections:
(0,0)─(0,1)─(1,0)
          │
        (2,1)─(2,2)

Traversal:
Start at (0,0), visit connected land cells, mark visited, then move to next unvisited land.

Myth Busters - 4 Common Misconceptions

Quick: Does diagonal adjacency count as connected land? Commit to yes or no.

Common Belief: Many think diagonal neighbors count as connected land for islands.

Reality: Only horizontal and vertical neighbors count as connected land, not diagonal.

Why it matters: Counting diagonals would merge separate islands incorrectly, giving wrong island counts.

Quick: Can BFS and DFS give different island counts? Commit to yes or no.

Common Belief: Some believe BFS and DFS might count different numbers of islands.

Reality: Both BFS and DFS always find the same number of islands because they explore connected components fully.

Why it matters: Misunderstanding this can cause confusion about which algorithm to use.

Quick: Is it safe to access neighbors without boundary checks? Commit to yes or no.

Common Belief: Some think you can check neighbors without verifying grid boundaries.

Reality: Accessing neighbors outside grid boundaries causes errors or crashes.

Why it matters: Ignoring boundaries leads to runtime errors and incorrect results.

Quick: Does marking visited cells require extra memory always? Commit to yes or no.

Common Belief: Many think you must always use a separate visited array.

Reality: You can mark visited cells in-place by modifying the grid, saving memory.

Why it matters: Knowing this helps write more memory-efficient code.

Expert Zone

1

DFS recursion depth can cause stack overflow on very large grids; iterative DFS or BFS avoids this.

2

In-place marking modifies input data, which may not be allowed in some contexts requiring a copy.

3

BFS can be extended to find shortest paths in grid problems, while DFS cannot guarantee shortest paths.

When NOT to use

Avoid BFS/DFS for counting islands if the grid is extremely large and memory is limited; consider Union-Find data structure for better performance. Also, if diagonal connections count, BFS/DFS must be adapted or replaced.

Production Patterns

Used in map analysis for geographic information systems, image segmentation in computer vision, and clustering in network analysis. BFS is preferred when shortest path or level information is needed; DFS is used for simpler connected component counting.

Connections

Graph Connected Components

Number of Islands is a special case of finding connected components in graphs.

Understanding islands as connected components helps apply graph theory algorithms broadly.

Flood Fill Algorithm

Flood fill uses similar BFS/DFS traversal to fill connected areas in images.

Knowing island counting helps understand how flood fill works in paint programs and games.

Epidemiology Spread Models

BFS models how diseases spread through connected populations, similar to exploring islands.

Seeing BFS in disease spread helps grasp traversal order and reachability concepts.

Common Pitfalls

#1 Not checking grid boundaries before accessing neighbors.

Wrong approach:

if grid[r-1][c] == '1' { dfs(r-1, c); }

Correct approach:

if r > 0 && grid[r-1][c] == '1' { dfs(r-1, c); }

Root cause:

Assuming neighbors always exist leads to out-of-bounds errors.

#2 Counting the same island multiple times by not marking visited cells.

Wrong approach:

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

Correct approach:

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

Root cause:

Not marking visited cells causes repeated counting of connected land.

#3 Using recursion without limit on large grids causing stack overflow.

Wrong approach:

fn dfs(r: usize, c: usize) { dfs(r+1, c); dfs(r-1, c); ... } // no stack limit

Correct approach:

Use iterative DFS with explicit stack or BFS with queue to avoid deep recursion.

Root cause:

Ignoring recursion depth limits in large inputs causes crashes.

Key Takeaways

Number of Islands problem counts connected groups of land cells in a grid using BFS or DFS.

Both BFS and DFS fully explore one island at a time, ensuring accurate counting without overlap.

Always check grid boundaries before accessing neighbors to avoid errors.

Mark visited cells to prevent counting the same island multiple times; in-place marking saves memory.

Choosing BFS or DFS depends on problem needs; BFS can find shortest paths, DFS is simpler and faster in some cases.

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