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. Each cell can be water or land, and connected means horizontally or vertically adjacent. BFS (Breadth-First Search) and DFS (Depth-First Search) are two ways to explore these groups to count them.

Why it matters

This problem helps understand how to explore connected parts in a grid, which is common in maps, games, and image processing. Without this, we couldn't easily find separate regions or clusters in data, making many applications inefficient or impossible.

Where it fits

You should know basic arrays and loops before this. After this, you can learn graph traversal algorithms, advanced grid problems, and connected components in graphs.

Mental Model

Core Idea

Explore each land cell and mark all connected land cells as visited to count distinct islands.

Think of it like...

Imagine a map with patches of forest separated by rivers. To count forests, you walk through one patch fully before moving to the next, so you don't count the same forest twice.

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

Islands found:
  Island 1: top-left block of 1s
  Island 2: middle 1
  Island 3: bottom-right block of 1s

Build-Up - 6 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 of 0s and 1s. 1 means land, 0 means water. Islands are groups of 1s connected horizontally or vertically. Diagonal connections do not count.

Result

You can identify which cells belong to land and which to water.

Knowing how the grid represents land and water is essential before exploring connected parts.

2

Foundation

Basic Traversal with DFS

Concept: Use Depth-First Search to explore connected land cells.

Start from a land cell, mark it visited, then recursively visit all adjacent land cells (up, down, left, right). This explores one island fully.

Result

You can visit all cells of one island starting from any land cell in it.

DFS helps explore all connected parts deeply before moving on, which is perfect for island counting.

3

Intermediate

Counting Islands Using DFS

🤔Before reading on: Do you think counting islands means visiting every cell once or multiple times? Commit to your answer.

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

Loop over each cell. If it's land and not visited, run DFS to mark the whole island visited and increase the island count by one.

Result

You get the total number of islands in the grid after checking all cells.

Understanding that each DFS call corresponds to one island prevents double counting.

4

Intermediate

Breadth-First Search (BFS) for Islands

🤔Before reading on: Will BFS visit cells in a different order than DFS? Commit to your answer.

Concept: Use BFS to explore islands level by level instead of deep first.

Start from a land cell, use a queue to visit neighbors in order. Mark visited cells to avoid repeats. BFS also fully explores one island before moving on.

Result

BFS also counts islands correctly, just explores cells in a different order.

Knowing BFS explores neighbors evenly helps understand alternative traversal strategies.

5

Advanced

Implementing BFS and DFS in C

🤔Before reading on: Do you think BFS or DFS is easier to implement in C? Commit to your answer.

Concept: Translate BFS and DFS logic into C code using arrays and queues or recursion.

Use a 2D array for the grid, a 2D boolean array for visited. For DFS, use recursion. For BFS, use a queue implemented with arrays or linked list. Mark visited cells to avoid revisiting.

Result

Complete C programs that output the number of islands for given grids.

Understanding how to implement these traversals in C solidifies the algorithm and memory management concepts.

6

Expert

Optimizations and Edge Cases

🤔Before reading on: Can you think of cases where BFS or DFS might be inefficient or cause errors? Commit to your answer.

Concept: Handle large grids, avoid stack overflow in DFS, and optimize memory usage.

For large grids, DFS recursion can cause stack overflow; BFS uses more memory but avoids this. Use iterative DFS with a stack to prevent overflow. Also, handle empty grids and all water or all land cases.

Result

Robust solutions that work efficiently on all inputs without crashing.

Knowing limitations and how to fix them prepares you for real-world coding challenges.

Under the Hood

Both DFS and BFS explore the grid by visiting connected land cells. DFS uses a call stack (or explicit stack) to go deep into one path before backtracking. BFS uses a queue to explore neighbors level by level. Visited cells are tracked to avoid infinite loops and double counting.

Why designed this way?

DFS and BFS come from graph theory to explore nodes and edges. Grids can be seen as graphs where each cell is a node connected to neighbors. These methods are simple, efficient, and guarantee visiting all connected nodes.

Grid cell connections:
┌───┬───┬───┐
│   │   │   │
├───┼───┼───┤
│   │ X │   │
├───┼───┼───┤
│   │   │   │
└───┴───┴───┘

X connects to up, down, left, right neighbors if they are land.

Myth Busters - 3 Common Misconceptions

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

Common Belief: Diagonal cells touching count as connected land for islands.

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

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

Quick: Is BFS always faster than DFS for this problem? Commit to yes or no.

Common Belief: BFS is always faster than DFS for counting islands.

Reality: Both have similar time complexity; speed depends on implementation and input size.

Why it matters: Choosing BFS just for speed can waste memory or cause complexity without real benefit.

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

Common Belief: You can count islands by just checking cells without marking visited.

Reality: Without marking visited, you will count the same island multiple times.

Why it matters: Not marking visited leads to overcounting and incorrect results.

Expert Zone

1

Iterative DFS using a stack avoids recursion limits and is preferred in production for large grids.

2

Modifying the input grid to mark visited cells saves memory but destroys original data, which may be unacceptable.

3

BFS can be optimized with early stopping if only counting islands without needing full traversal.

When NOT to use

For extremely large grids or streaming data, union-find (disjoint set) data structures can be more efficient. Also, if diagonal connections count, BFS/DFS logic must be adjusted or replaced.

Production Patterns

In real systems, grids may be sparse; using adjacency lists or compressed representations improves performance. Also, parallel BFS/DFS can speed up counting on large maps.

Connections

Graph Connected Components

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

Understanding islands as connected components helps apply graph algorithms broadly.

Image Segmentation in Computer Vision

Both involve grouping connected pixels or regions based on similarity.

Knowing island counting aids in understanding how images are divided into meaningful parts.

Epidemiology Spread Models

Exploring connected regions is similar to tracing infection spread through contact networks.

Techniques for island counting help model and analyze disease spread patterns.

Common Pitfalls

#1 Not marking visited cells causes repeated counting of the same island.

Wrong approach:

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

// No visited array or marking

Correct approach:

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

Root cause:

Without visited tracking, recursion loops infinitely or counts islands multiple times.

#2 Counting diagonal neighbors as connected land.

Wrong approach:

Check neighbors including diagonals:
for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
if (dr != 0 || dc != 0) dfs(r+dr, c+dc);
}
}

Correct approach:

Check only up, down, left, right neighbors:
int directions[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
for (int i=0; i<4; i++) {
dfs(r+directions[i][0], c+directions[i][1]);
}

Root cause:

Misunderstanding adjacency rules leads to merging separate islands.

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

Wrong approach:

Recursive DFS without limits on large input causes crash.

Correct approach:

Use iterative DFS with explicit stack:
stack.push(start);
while (!stack.empty()) {
cell = stack.pop();
// process and push neighbors
}

Root cause:

Recursion depth exceeds system limits on large inputs.

Key Takeaways

Number of Islands problem counts connected groups of land cells in a grid using graph traversal.

DFS and BFS are two main ways to explore and mark visited cells to avoid double counting.

Only horizontal and vertical neighbors count as connected, not diagonals.

Marking visited cells is essential to prevent infinite loops and overcounting.

Implementations must handle large inputs carefully to avoid stack overflow or memory issues.

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 longest path of '1's in the grid

B. Count how many groups of connected '1's (islands) are in the grid

C. Calculate the total number of '0's in the grid

D. Replace all '1's with '0's in the grid

Solution

1. Step 1: Understand the problem definition

   The problem asks to find how many separate groups of connected '1's exist in the grid. Each group is called an island.

2. Step 2: Identify what is counted

   We count each cluster of adjacent '1's (connected horizontally or vertically) as one island.

3. Final Answer:

   Count how many groups of connected '1's (islands) are in the grid -> Option B

4. Quick Check:

   Number of islands = count of connected '1' groups [OK]

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

Common Mistakes:

• Counting individual '1's instead of groups
• Including diagonal connections as connected
• Counting '0's instead of '1's

2. Which of the following is the correct way to start a DFS function to explore neighbors in a grid for the Number of Islands problem in C?

easy

A. int dfs(int row, int col, char* grid)

B. int dfs(char grid[][], int row, int col)

C. void dfs(int row, int col, int grid[][])

D. void dfs(int row, int col, char** grid, int rows, int cols)

Solution

1. Step 1: Check parameter types for grid and indices

   The grid is a 2D array of characters, passed as char** grid. Row and col are integers. Rows and cols are needed to check boundaries.

2. Step 2: Verify function signature matches common DFS pattern

   void dfs(int row, int col, char** grid, int rows, int cols) correctly uses void return type (no return needed), takes row, col, grid pointer, and grid size parameters.

3. Final Answer:

   void dfs(int row, int col, char** grid, int rows, int cols) -> Option D

4. Quick Check:

   Correct DFS signature includes grid pointer and size [OK]

Hint: DFS needs grid pointer, indices, and grid size [OK]

Common Mistakes:

• Using incorrect grid parameter type
• Missing grid size parameters
• Wrong return type for DFS

3. Given the grid:

char* grid[] = {"11000", "11000", "00100", "00011"};
int rows = 4, cols = 5;

What is the number of islands found by a correct BFS or DFS solution?

medium

A. 3

B. 2

C. 1

D. 4

Solution

1. Step 1: Visualize the grid and connected '1's

   Grid rows:
   Row 0: 1 1 0 0 0
   Row 1: 1 1 0 0 0
   Row 2: 0 0 1 0 0
   Row 3: 0 0 0 1 1
   Islands are groups of connected '1's horizontally or vertically.

2. Step 2: Count islands by grouping connected '1's

   Island 1: Top-left block (positions (0,0),(0,1),(1,0),(1,1))
   Island 2: Middle single '1' at (2,2)
   Island 3: Bottom-right block (positions (3,3),(3,4))
   Total islands = 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Count connected '1' groups = 3 [OK]

Hint: Count connected '1' clusters visually [OK]

Common Mistakes:

• Counting diagonal '1's as connected
• Missing isolated single '1's
• Misreading grid rows or columns

4. In the following DFS code snippet for Number of Islands, what is the bug?

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

medium

A. It does not check for visited cells, causing infinite recursion

B. It modifies the grid, which is not allowed

C. It correctly marks visited cells by setting '1' to '0', no bug

D. It misses diagonal neighbors in DFS

Solution

1. Step 1: Analyze how visited cells are handled

   The code sets grid[r][c] = '0' to mark visited cells, preventing revisiting.

2. Step 2: Check if this approach is valid and complete

   Marking visited by changing '1' to '0' is a common and valid method. The code checks boundaries and stops recursion correctly.

3. Final Answer:

   It correctly marks visited cells by setting '1' to '0', no bug -> Option C

4. Quick Check:

   Mark visited by changing '1' to '0' is correct [OK]

Hint: Mark visited by changing '1' to '0' is valid [OK]

Common Mistakes:

• Thinking grid modification is always wrong
• Expecting separate visited array
• Confusing diagonal neighbors as required

5. You have a grid with 1000 rows and 1000 columns filled mostly with '0's and a few scattered '1's forming small islands. Which approach is best to efficiently count islands and why?

hard

A. Use BFS with a queue to avoid deep recursion and handle large grid efficiently

B. Use DFS with recursion because it is simpler and faster for large grids

C. Use DFS but do not mark visited cells to save memory

D. Count '1's directly without traversal to save time

Solution

1. Step 1: Consider grid size and recursion limits

   A 1000x1000 grid is large. Recursive DFS may cause stack overflow due to deep recursion.

2. Step 2: Evaluate BFS advantages for large grids

   BFS uses an explicit queue and avoids deep recursion, making it safer and efficient for large grids.

3. Step 3: Check other options for correctness

   DFS without marking visited causes infinite loops. Counting '1's directly misses island grouping.

4. Final Answer:

   Use BFS with a queue to avoid deep recursion and handle large grid efficiently -> Option A

5. Quick Check:

   Large grid + avoid recursion overflow = BFS [OK]

Hint: Use BFS to avoid recursion limits on large grids [OK]

Common Mistakes:

• Using recursive DFS causing stack overflow
• Not marking visited cells causing infinite loops
• Counting '1's without grouping