Number of Islands BFS and DFS in DSA C#

Mental Model

We find groups of connected land cells in a grid by exploring neighbors until all connected parts are visited.

Analogy: Imagine a map with islands made of connected land squares. We walk around each island fully before moving to the next one.

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

1 = land, 0 = water
We want to count how many separate islands (groups of 1s) exist.

Dry Run Walkthrough

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

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

Step 1: Start scanning from top-left cell (0,0), found land (1), start BFS/DFS to mark connected land.

Visited cells marked: (0,0), (0,1), (1,0), (1,1)
Grid with visited marked as X:
X X 0 0
X X 0 1
0 0 1 1

Why: We found the first island and mark all connected land to avoid counting it again.

Step 2: Continue scanning, skip visited land cells, reach cell (1,3) which is land and unvisited, start BFS/DFS.

Visited cells now include (1,3), (2,2), (2,3)
Grid with visited marked as X:
X X 0 0
X X 0 X
0 0 X X

Why: Found second island, mark all connected land cells.

Step 3: Finish scanning all cells, no more unvisited land found.

All islands counted: 2

Why: All land cells are visited and grouped, so counting is complete.

Result:

Final count: 2 islands

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class NumberOfIslands {
    static int Rows, Cols;

    public static int NumIslandsBFS(int[][] grid) {
        if (grid == null || grid.Length == 0) return 0;
        Rows = grid.Length;
        Cols = grid[0].Length;
        bool[][] visited = new bool[Rows][];
        for (int i = 0; i < Rows; i++) visited[i] = new bool[Cols];

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

    static void BFS(int[][] grid, bool[][] visited, int r, int c) {
        int[] dr = new int[] { -1, 1, 0, 0 };
        int[] dc = new int[] { 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 < Rows && nc >= 0 && nc < Cols &&
                    grid[nr][nc] == 1 && !visited[nr][nc]) {
                    queue.Enqueue((nr, nc));
                    visited[nr][nc] = true;
                }
            }
        }
    }

    public static int NumIslandsDFS(int[][] grid) {
        if (grid == null || grid.Length == 0) return 0;
        Rows = grid.Length;
        Cols = grid[0].Length;
        bool[][] visited = new bool[Rows][];
        for (int i = 0; i < Rows; i++) visited[i] = new bool[Cols];

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

    static void DFS(int[][] grid, bool[][] visited, int r, int c) {
        if (r < 0 || r >= Rows || c < 0 || c >= Cols) return;
        if (grid[r][c] == 0 || visited[r][c]) return;

        visited[r][c] = true;
        DFS(grid, visited, r - 1, c);
        DFS(grid, visited, r + 1, c);
        DFS(grid, visited, r, c - 1);
        DFS(grid, visited, r, c + 1);
    }

    static void Main() {
        int[][] grid = new int[][] {
            new int[] {1,1,0,0},
            new int[] {1,1,0,1},
            new int[] {0,0,1,1}
        };

        Console.WriteLine("Number of islands (BFS): " + NumIslandsBFS(grid));
        Console.WriteLine("Number of islands (DFS): " + NumIslandsDFS(grid));
    }
}

if (grid[r][c] == 1 && !visited[r][c]) {

Check for unvisited land cell to start BFS/DFS

BFS(grid, visited, r, c);

Start BFS to mark all connected land cells

visited[r][c] = true;

Mark current cell as visited to avoid revisiting

queue.Enqueue((r, c));

Add starting cell to BFS queue

var (row, col) = queue.Dequeue();

Process next cell in BFS queue

if (nr >= 0 && nr < Rows && nc >= 0 && nc < Cols && grid[nr][nc] == 1 && !visited[nr][nc]) {

Check neighbor is valid land and unvisited

DFS(grid, visited, r - 1, c);

Recursively visit up neighbor in DFS

DFS(grid, visited, r + 1, c);

Recursively visit down neighbor in DFS

DFS(grid, visited, r, c - 1);

Recursively visit left neighbor in DFS

DFS(grid, visited, r, c + 1);

Recursively visit right neighbor in DFS

Output

Number of islands (BFS): 2

Number of islands (DFS): 2

Complexity Analysis

Time: O(R*C) because we visit each cell at most once during BFS or DFS

Space: O(R*C) for the visited array and BFS queue or DFS recursion stack in worst case

vs Alternative: Compared to naive repeated scanning without marking visited, BFS/DFS avoids reprocessing cells, reducing time from potentially O((R*C)^2) to O(R*C)

Edge Cases

Empty grid

Returns 0 islands immediately

DSA C#

if (grid == null || grid.Length == 0) return 0;

Grid with all water (0s)

Returns 0 islands as no land found

DSA C#

if (grid[r][c] == 1 && !visited[r][c]) {

Grid with one big island (all 1s)

Returns 1 island after marking all cells visited

DSA C#

visited[r][c] = true;

When to Use This Pattern

When you see a grid and need to find connected groups of cells, use BFS or DFS to explore neighbors and mark visited to count distinct islands.

Common Mistakes

Mistake: Not marking visited cells, causing infinite loops or double counting
Fix: Always mark cells as visited when you add them to queue or visit in DFS

Mistake: Checking neighbors outside grid boundaries
Fix: Add boundary checks before accessing neighbors

Summary

Counts how many groups of connected land cells exist in a grid using BFS or DFS.

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

The key is to explore all connected neighbors from each unvisited land cell to avoid double counting.

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