Number of Islands BFS and DFS in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BFS-based Number of Islands

What is the output of the following C# code that counts islands using BFS?

DSA C#

using System;
using System.Collections.Generic;

class Solution {
    public int NumIslands(char[][] grid) {
        if (grid == null || grid.Length == 0) return 0;
        int count = 0;
        int rows = grid.Length;
        int cols = grid[0].Length;
        bool[][] visited = new bool[rows][];
        for (int i = 0; i < rows; i++) visited[i] = new bool[cols];

        int[][] directions = new int[][] {
            new int[] {1, 0},
            new int[] {-1, 0},
            new int[] {0, 1},
            new int[] {0, -1}
        };

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1' && !visited[r][c]) {
                    count++;
                    Queue<(int, int)> queue = new Queue<(int, int)>();
                    queue.Enqueue((r, c));
                    visited[r][c] = true;

                    while (queue.Count > 0) {
                        var (row, col) = queue.Dequeue();
                        foreach (var dir in directions) {
                            int nr = row + dir[0];
                            int nc = col + dir[1];
                            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
                                grid[nr][nc] == '1' && !visited[nr][nc]) {
                                queue.Enqueue((nr, nc));
                                visited[nr][nc] = true;
                            }
                        }
                    }
                }
            }
        }
        return count;
    }
}

class Program {
    static void Main() {
        char[][] grid = new char[][] {
            new char[] {'1','1','0','0','0'},
            new char[] {'1','1','0','0','0'},
            new char[] {'0','0','1','0','0'},
            new char[] {'0','0','0','1','1'}
        };
        Solution sol = new Solution();
        Console.WriteLine(sol.NumIslands(grid));
    }
}

A 3

B 1

C 4

D 2

💡 Hint

Count connected groups of '1's using BFS traversal.

The grid has three separate islands: one in the top-left corner, one in the middle, and one in the bottom-right corner.

❓ Predict Output

intermediate

Output of DFS-based Number of Islands

What is the output of the following C# code that counts islands using DFS?

DSA C#

using System;

class Solution {
    private int rows, cols;
    private char[][] grid;

    public int NumIslands(char[][] grid) {
        if (grid == null || grid.Length == 0) return 0;
        this.grid = grid;
        rows = grid.Length;
        cols = grid[0].Length;
        int count = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1') {
                    count++;
                    DFS(r, c);
                }
            }
        }
        return count;
    }

    private void DFS(int r, int c) {
        if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] == '0') return;
        grid[r][c] = '0';
        DFS(r + 1, c);
        DFS(r - 1, c);
        DFS(r, c + 1);
        DFS(r, c - 1);
    }
}

class Program {
    static void Main() {
        char[][] grid = new char[][] {
            new char[] {'1','1','0','0','0'},
            new char[] {'1','1','0','0','0'},
            new char[] {'0','0','1','0','0'},
            new char[] {'0','0','0','1','1'}
        };
        Solution sol = new Solution();
        Console.WriteLine(sol.NumIslands(grid));
    }
}

A 4

B 2

C 3

D 1

💡 Hint

DFS marks connected land as water to avoid recounting.

The DFS visits and marks all connected '1's in each island, counting 3 islands total.

🧠 Conceptual

advanced

Why BFS or DFS is suitable for Number of Islands?

Why are BFS and DFS algorithms suitable for solving the Number of Islands problem?

A Because they explore all connected land cells systematically to identify islands.

B Because they sort the grid cells to group islands together.

C Because they use hashing to store island coordinates efficiently.

D Because they convert the grid into a binary tree for easier traversal.

💡 Hint

Think about how connected components are found in a grid.

BFS and DFS explore all connected land cells (neighbors) starting from one land cell, which helps identify each island as a connected component.

🔧 Debug

advanced

Identify the bug in this DFS code snippet

What error will this DFS code cause when counting islands?

DSA C#

private void DFS(int r, int c) {
    if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] == '0') return;
    DFS(r + 1, c);
    DFS(r - 1, c);
    DFS(r, c + 1);
    DFS(r, c - 1);
}

A NullReferenceException because grid is not initialized.

B No error, code works correctly.

C IndexOutOfRangeException due to wrong boundary checks.

D StackOverflowException due to missing base case to mark visited cells.

💡 Hint

Check if visited cells are marked to avoid infinite recursion.

The code does not mark visited land cells as water or visited, so it revisits the same cells infinitely causing stack overflow.

🚀 Application

expert

Optimizing Number of Islands for large grids

Which approach best optimizes counting islands in a very large grid with mostly water?

A Use DFS without marking visited cells to save memory.

B Use a Union-Find data structure to merge connected lands efficiently.

C Use BFS with early stopping when water cells are encountered to skip unnecessary checks.

D Convert the grid to a list and sort it to group islands.

💡 Hint

Think about data structures that efficiently merge connected components.

Union-Find (Disjoint Set) efficiently merges connected land cells and counts islands with near constant time operations, suitable for large grids.

Practice

1. What does the "Number of Islands" problem typically ask you to find in a 2D grid?

easy

A. Calculate the perimeter of islands

B. Find the largest island size

C. Replace all '1's with '0's

D. Count how many groups of connected '1's (land) exist

Solution

1. Step 1: Understand the problem statement

   The problem asks to count distinct islands, where islands are groups of connected '1's (land) in the grid.

2. Step 2: Identify what is being counted

   We count how many separate groups of connected land cells exist, not their size or perimeter.

3. Final Answer:

   Count how many groups of connected '1's (land) exist -> Option D

4. Quick Check:

   Number of islands = count of connected land groups [OK]

Hint: Islands = connected groups of '1's in grid [OK]

Common Mistakes:

• Confusing island count with island size
• Counting water cells instead of land
• Ignoring connectivity rules (horizontal and vertical)

2. Which of the following C# code snippets correctly initializes a 2D char array representing a grid for the Number of Islands problem?

easy

A. char[,] grid = new char[][] { {'1','0'}, {'0','1'} };

B. char[,] grid = { {'1','0'}, {'0','1'} };

C. char[][] grid = new char[][] { new char[] {'1','0'}, new char[] {'0','1'} };

D. char[][] grid = new char[2][2] { {'1','0'}, {'0','1'} };

Solution

1. Step 1: Understand C# 2D array initialization

   In C#, jagged arrays (array of arrays) are declared as char[][] and initialized with new char[][] and inner arrays. Number of Islands uses jagged arrays for grid[r][c] access and grid[0].Length.

2. Step 2: Check each option's syntax

   char[][] grid = new char[][] { new char[] {'1','0'}, new char[] {'0','1'} };: char[][] grid = new char[][] { new char[] {'1','0'}, new char[] {'0','1'} }; correctly uses jagged array syntax.
   char[,] grid = new char[][] { {'1','0'}, {'0','1'} };: declares char[,] (rectangular) but tries jagged init - type mismatch.
   char[,] grid = { {'1','0'}, {'0','1'} };: valid rectangular char[,], but incompatible with grid[r][c] and grid[0].Length.
   char[][] grid = new char[2][2] { {'1','0'}, {'0','1'} };: new char[2][2] invalid syntax (incorrect brackets).

3. Final Answer:

   char[][] grid = new char[][] { new char[] {'1','0'}, new char[] {'0','1'} }; -> Option C

4. Quick Check:

   Jagged array with new keyword = correct syntax [OK]

Hint: Use 'new' keyword for jagged arrays in C# [OK]

Common Mistakes:

• Omitting 'new' keyword in array initialization
• Confusing jagged arrays with rectangular arrays
• Using wrong braces or missing inner arrays

3. Given the following grid and BFS-based code snippet, what is the output (number of islands)?

char[][] grid = new char[][] {
  new char[] {'1','1','0','0'},
  new char[] {'1','0','0','1'},
  new char[] {'0','0','1','1'},
  new char[] {'0','0','0','0'}
};

int CountIslands(char[][] grid) {
  int count = 0;
  int rows = grid.Length;
  int cols = grid[0].Length;
  bool[][] visited = new bool[rows][];
  for (int i = 0; i < rows; i++) visited[i] = new bool[cols];

  for (int r = 0; r < rows; r++) {
    for (int c = 0; c < cols; c++) {
      if (grid[r][c] == '1' && !visited[r][c]) {
        BFS(r, c, grid, visited);
        count++;
      }
    }
  }
  return count;
}

void BFS(int r, int c, char[][] grid, bool[][] visited) {
  int[] dr = { -1, 1, 0, 0 };
  int[] dc = { 0, 0, -1, 1 };
  Queue<(int, int)> queue = new Queue<(int, int)>();
  queue.Enqueue((r, c));
  visited[r][c] = true;

  while (queue.Count > 0) {
    var (row, col) = queue.Dequeue();
    for (int i = 0; i < 4; i++) {
      int nr = row + dr[i];
      int nc = col + dc[i];
      if (nr >= 0 && nr < grid.Length && nc >= 0 && nc < grid[0].Length && grid[nr][nc] == '1' && !visited[nr][nc]) {
        queue.Enqueue((nr, nc));
        visited[nr][nc] = true;
      }
    }
  }
}

Console.WriteLine(CountIslands(grid));

medium

A. 3

B. 2

C. 4

D. 1

Solution

1. Step 1: Analyze the grid for connected islands

   Islands are groups of '1's connected horizontally or vertically. The grid has these islands:
   - Island 1: (0,0),(0,1),(1,0)
   - Island 2: (1,3)
   - Island 3: (2,2),(2,3)

2. Step 2: BFS visits each island once

   The BFS marks all connected '1's as visited. Each BFS call increments count by 1. Total BFS calls = number of islands = 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Count islands by BFS calls = 3 [OK]

Hint: Count BFS calls on unvisited '1's = number of islands [OK]

Common Mistakes:

• Counting diagonally connected '1's as one island
• Missing isolated single '1's as islands
• Not marking visited cells properly

4. Identify the bug in the following DFS code for counting islands and select the correct fix:

void DFS(int r, int c, char[][] grid, bool[][] visited) {
  if (r < 0 || r >= grid.Length || c < 0 || c >= grid[0].Length || grid[r][c] == '0')
    return;
  visited[r][c] = true;
  DFS(r - 1, c, grid, visited);
  DFS(r + 1, c, grid, visited);
  DFS(r, c - 1, grid, visited);
  DFS(r, c + 1, grid, visited);
}

int CountIslands(char[][] grid) {
  int count = 0;
  int rows = grid.Length;
  int cols = grid[0].Length;
  bool[][] visited = new bool[rows][];
  for (int i = 0; i < rows; i++) visited[i] = new bool[cols];

  for (int r = 0; r < rows; r++) {
    for (int c = 0; c < cols; c++) {
      if (grid[r][c] == '1' && !visited[r][c]) {
        DFS(r, c, grid, visited);
        count++;
      }
    }
  }
  return count;
}

medium

A. Change grid[r][c] == '0' to grid[r][c] == '1' in base case

B. Add a check for visited[r][c] before recursive DFS calls

C. Initialize visited array with 'true' instead of 'false'

D. Remove visited array and rely on grid modification

Solution

1. Step 1: Identify missing visited check in DFS

   The DFS function does not check if a cell is already visited before recursive calls, causing infinite recursion or revisiting.

2. Step 2: Fix by adding visited check before recursion

   Adding "if (visited[r][c]) return;" before marking visited prevents revisiting cells and infinite loops.

3. Final Answer:

   Add a check for visited[r][c] before recursive DFS calls -> Option B

4. Quick Check:

   Prevent revisiting by checking visited before DFS calls [OK]

Hint: Always check visited before DFS recursion to avoid loops [OK]

Common Mistakes:

• Not checking visited before recursion
• Confusing base case conditions
• Modifying grid instead of using visited array

5. You want to modify the Number of Islands solution to count islands considering diagonal connections as well (8 directions). Which change is needed in the BFS or DFS traversal?

hard

A. Add diagonal directions (-1,-1), (-1,1), (1,-1), (1,1) to the direction arrays

B. Only check horizontal neighbors, ignore vertical and diagonal

C. Use a stack instead of a queue for BFS

D. Change grid cells from '1' to '2' when visited

Solution

1. Step 1: Understand connectivity rules

   Original problem connects cells horizontally and vertically (4 directions). To include diagonals, add those directions.

2. Step 2: Modify direction arrays for 8 directions

   Add diagonal moves (-1,-1), (-1,1), (1,-1), (1,1) to dr and dc arrays to explore all neighbors.

3. Final Answer:

   Add diagonal directions (-1,-1), (-1,1), (1,-1), (1,1) to the direction arrays -> Option A

4. Quick Check:

   Include diagonals by adding their directions [OK]

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

Common Mistakes:

• Ignoring diagonal neighbors
• Confusing BFS and DFS data structures
• Changing grid values instead of using visited array