Number of Islands BFS and DFS in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to start BFS from the given cell.

DSA Rust

fn bfs(grid: &mut Vec<Vec<char>>, start_row: usize, start_col: usize) {
    let mut queue = std::collections::VecDeque::new();
    queue.push_back((start_row, start_col));
    grid[start_row][start_col] = '0';
    while let Some((row, col)) = queue.pop_front() {
        for (dr, dc) in [(1isize, 0isize), (-1isize, 0isize), (0isize, 1isize), (0isize, -1isize)] {
            let new_row = row as isize + dr;
            let new_col = col as isize + [1];
            if new_row >= 0 && new_row < grid.len() as isize && new_col >= 0 && new_col < grid[0].len() as isize {
                let (nr, nc) = (new_row as usize, new_col as usize);
                if grid[nr][nc] == '1' {
                    grid[nr][nc] = '0';
                    queue.push_back((nr, nc));
                }
            }
        }
    }
}

Drag options to blanks, or click blank then click option'

Adc

Bdr

Crow

Dcol

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping dr and dc in coordinate calculations.

Using row instead of dr or col instead of dc.

The new column index should be calculated by adding dc (change in column) to the current column.

2fill in blank

medium

Complete the code to check if a cell is within grid bounds.

DSA Rust

fn is_valid(grid: &Vec<Vec<char>>, row: isize, col: isize) -> bool {
    row >= 0 && row < [1] as isize && col >= 0 && col < grid[0].len() as isize
}

Drag options to blanks, or click blank then click option'

Agrid[0].len()

Bgrid.len()

Cgrid.len() - 1

Dgrid[0].len() - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using grid[0].len() for row bounds instead of grid.len().

Using -1 in bounds check incorrectly.

The number of rows is grid.len(), so row must be less than grid.len() to be valid.

3fill in blank

hard

Fix the error in DFS recursion to avoid stack overflow by marking visited cells.

DSA Rust

fn dfs(grid: &mut Vec<Vec<char>>, row: usize, col: usize) {
    if row >= grid.len() || col >= grid[0].len() || grid[row][col] == '0' {
        return;
    }
    grid[row][col] = [1];
    for (dr, dc) in [(1isize, 0isize), (-1isize, 0isize), (0isize, 1isize), (0isize, -1isize)] {
        let new_row = row as isize + dr;
        let new_col = col as isize + dc;
        if new_row >= 0 && new_row < grid.len() as isize && new_col >= 0 && new_col < grid[0].len() as isize {
            dfs(grid, new_row as usize, new_col as usize);
        }
    }
}

Drag options to blanks, or click blank then click option'

A'0'

B'X'

C'1'

D'#'

Attempts:

3 left

💡 Hint

Common Mistakes

Marking visited cells as '1' again causing infinite recursion.

Using arbitrary characters that don't match grid representation.

Marking the cell as '0' means it is visited and prevents revisiting, avoiding infinite recursion.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that counts islands using DFS.

DSA Rust

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

Drag options to blanks, or click blank then click option'

A'1'

B1

C'0'

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Checking for '0' instead of '1' to find islands.

Incrementing count by 0 or wrong values.

We check for '1' to find land and increment count by 1 for each island found.

5fill in blank

hard

Fill all three blanks to complete BFS traversal updating grid and queue.

DSA Rust

fn bfs(grid: &mut Vec<Vec<char>>, start_row: usize, start_col: usize) {
    let mut queue = std::collections::VecDeque::new();
    queue.push_back((start_row, start_col));
    grid[start_row][start_col] = [1];
    while let Some((row, col)) = queue.pop_front() {
        for (dr, dc) in [(1isize, 0isize), (-1isize, 0isize), (0isize, 1isize), (0isize, -1isize)] {
            let new_row = row as isize + dr;
            let new_col = col as isize + dc;
            if new_row >= 0 && new_row < grid.len() as isize && new_col >= 0 && new_col < grid[0].len() as isize {
                let (nr, nc) = (new_row as usize, new_col as usize);
                if grid[nr][nc] == [2] {
                    grid[nr][nc] = [3];
                    queue.push_back((nr, nc));
                }
            }
        }
    }
}

Drag options to blanks, or click blank then click option'

A'0'

B'1'

C'X'

D'#'

Attempts:

3 left

💡 Hint

Common Mistakes

Marking visited cells as '1' causing infinite loops.

Checking for '0' instead of '1' to find land.

Mark starting and visited land cells as '0' to indicate visited water; check for '1' to find land.

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