Number of Islands BFS and DFS in DSA C# - 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 of water and land. Each cell can be either land or water, and connected land cells form an island. We use BFS (Breadth-First Search) or DFS (Depth-First Search) to explore and mark these connected lands. This helps us find all islands without counting any twice.

Why it matters

Without this method, we would struggle to identify separate islands in a grid, which is important in many real-world problems like mapping, image processing, and network connectivity. It helps computers understand clusters or groups in data. Without it, tasks like finding isolated areas or connected components would be inefficient or impossible.

Where it fits

Before this, you should understand basic arrays and grids, and simple loops. After this, you can learn more complex graph traversal algorithms, connected components in graphs, and problems involving grid-based pathfinding.

Mental Model

Core Idea

Explore each land cell and mark all connected land cells as one island using BFS or DFS to avoid counting them multiple times.

Think of it like...

Imagine you are coloring a map where each island is a country. Once you start coloring one country, you color all connected parts before moving to the next country, so you never color the same country twice.

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 block of 1s
  Island 2: middle-right block of 1s
  Island 3: bottom-left single 1
  Island 4: bottom-middle single 1
  Island 5: bottom-right single 1

Build-Up - 6 Steps

1

Foundation

Understanding the Grid and Islands

Concept: Introduce the grid structure and what counts as land or water.

A grid is a 2D array where each cell is either '1' (land) or '0' (water). Islands are groups of '1's connected horizontally or vertically (not diagonally). The goal is to count how many such groups exist.

Result

You can identify individual cells as land or water and understand that connected lands form islands.

Knowing the problem setup clearly helps you visualize what you need to find and why simple counting won't work.

2

Foundation

Basic Traversal with DFS

Concept: Use Depth-First Search to explore connected land cells from a starting point.

Starting from a land cell, DFS visits all connected land cells by moving up, down, left, and right recursively. Mark visited cells to avoid revisiting. This way, one DFS call covers one island.

Result

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

Understanding DFS as a way to fully explore connected parts prevents double counting and forms the basis for counting islands.

3

Intermediate

Implementing BFS for Island Exploration

🤔Before reading on: do you think BFS will explore connected land cells in the same order as DFS? Commit to your answer.

Concept: Breadth-First Search explores neighbors level by level using a queue, instead of going deep first like DFS.

From a land cell, BFS adds all adjacent land cells to a queue and processes them one by one, marking visited cells. This also covers one island fully before moving on.

Result

BFS can also find and mark all connected land cells of an island, just in a different order than DFS.

Knowing BFS explores neighbors in layers helps understand different traversal orders and their effects on performance and memory.

4

Intermediate

Marking Visited Cells to Avoid Recounts

🤔Before reading on: do you think it's enough to just count land cells without marking them visited? Commit to your answer.

Concept: To avoid counting the same island multiple times, visited land cells must be marked so they are not counted again.

When a land cell is visited during BFS or DFS, change its value or keep a separate visited array to mark it. This prevents revisiting and recounting the same island.

Result

Each island is counted exactly once, ensuring correct total count.

Understanding the importance of marking visited cells prevents logical errors and infinite loops.

5

Advanced

Handling Edge Cases and Grid Boundaries

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

Concept: When exploring neighbors, ensure you do not go outside the grid boundaries to avoid errors.

Before visiting a neighbor cell, check if its row and column indices are within the grid limits. Skip neighbors that are out of bounds.

Result

The algorithm runs safely without errors or crashes due to invalid indices.

Knowing how to safely handle boundaries is crucial for robust grid traversal algorithms.

6

Expert

Optimizing Space by Modifying Input Grid

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

Concept: Instead of using extra space for visited cells, modify the input grid to mark visited land cells by changing '1' to '0'.

When a land cell is visited, set it to '0' to mark it as water, effectively marking it visited. This saves memory but changes the input.

Result

The algorithm uses less memory but the original grid is altered.

Understanding this tradeoff helps balance memory use and data preservation depending on the problem context.

Under the Hood

BFS and DFS work by exploring nodes (cells) in a graph (grid) structure. Each land cell is a node connected to its adjacent land nodes. DFS uses a stack (often via recursion) to explore as deep as possible before backtracking. BFS uses a queue to explore neighbors level by level. Both mark visited nodes to avoid cycles and repeated work.

Why designed this way?

These methods come from graph theory to efficiently explore connected components. DFS is simple and uses recursion, while BFS guarantees shortest path layers. Marking visited nodes prevents infinite loops and double counting. Alternatives like union-find exist but BFS/DFS are intuitive and easy to implement on grids.

Grid cell connections:

  [1]─[1]   [0]   [0]   [0]
   │    
  [1]─[1]   [0]   [0]─[1]
                 │     │
  [0]   [0]   [0]   [1]─[1]

Traversal flow:

Start at a '1' cell
  ↓
Mark visited
  ↓
Explore neighbors (up, down, left, right)
  ↓
Repeat until no new neighbors
  ↓
One island fully explored

Myth Busters - 3 Common Misconceptions

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

Common Belief: Some think diagonally touching land cells form one island.

Reality: Only horizontal and vertical neighbors count as connected; diagonals do not connect islands.

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

Quick: Can you count islands without marking visited cells? Commit to yes or no.

Common Belief: You can just count every land cell and get the number of islands.

Reality: Without marking visited cells, you count parts of the same island multiple times, inflating the count.

Why it matters: This leads to incorrect results and logical errors in the algorithm.

Quick: Does BFS always use less memory than DFS? Commit to yes or no.

Common Belief: BFS is always more memory efficient than DFS.

Reality: BFS can use more memory because it stores all neighbors in a queue, while DFS uses recursion stack which can be smaller or larger depending on the grid shape.

Why it matters: Choosing BFS or DFS affects performance and memory; misunderstanding this can cause inefficiency or stack overflow.

Expert Zone

1

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

2

Modifying the input grid to mark visited cells is memory efficient but destroys original data, which may be unacceptable in some cases.

3

BFS can be used to find shortest paths on grids, while DFS cannot guarantee shortest paths.

When NOT to use

Avoid BFS/DFS when the grid is extremely large and recursion depth is limited; use iterative methods or union-find data structures instead. Also, if you need to preserve the input grid, use a separate visited array.

Production Patterns

In real systems, BFS and DFS are used for image segmentation, network connectivity checks, and game map analysis. Often, iterative BFS with a queue is preferred for stability and memory control. Marking visited cells in-place is common in memory-constrained environments.

Connections

Graph Connected Components

Number of Islands is a special case of finding connected components in an undirected graph.

Understanding islands as connected components generalizes the problem to many graph algorithms.

Flood Fill Algorithm

Flood fill uses similar BFS/DFS traversal to fill connected areas, like painting an island.

Knowing flood fill helps understand how BFS/DFS can be used to modify or analyze connected regions.

Epidemiology Spread Models

The way BFS/DFS explores connected cells is similar to how diseases spread through connected populations.

Recognizing this connection shows how traversal algorithms model real-world spreading phenomena.

Common Pitfalls

#1 Not marking visited cells leads to counting the same island multiple times.

Wrong approach:

foreach cell in grid:
if cell == '1':
count++
// no marking visited

Correct approach:

foreach cell in grid:
if cell == '1':
count++
DFS or BFS to mark all connected '1's as visited

Root cause:

Misunderstanding that connected land cells must be grouped and counted once.

#2 Checking neighbors without boundary checks causes errors or crashes.

Wrong approach:

Visit neighbors at (row-1, col), (row+1, col), (row, col-1), (row, col+1) without verifying indices.

Correct approach:

Before visiting neighbors, check if indices are within grid bounds to avoid invalid access.

Root cause:

Forgetting that grid edges have no neighbors beyond boundaries.

#3 Using recursion for DFS on large grids causes stack overflow.

Wrong approach:

Recursive DFS calls without limit on large grids.

Correct approach:

Use iterative DFS with an explicit stack or BFS with a queue to avoid recursion limits.

Root cause:

Not considering system recursion depth limits.

Key Takeaways

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

Marking visited cells is essential to avoid counting the same island multiple times.

BFS explores neighbors level by level using a queue; DFS explores deeply using recursion or a stack.

Handling grid boundaries prevents errors during neighbor exploration.

Modifying the input grid can save memory but may not always be acceptable.

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