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

Why it matters

This problem helps us understand how to explore connected areas in grids, which is useful in maps, games, and image processing. Without this, we couldn't easily find or count clusters in data, making many applications inefficient or impossible.

Where it fits

Before this, you should know basic arrays and how to traverse them. After this, you can learn more complex graph algorithms and grid-based problems like shortest path or maze solving.

Mental Model

Core Idea

To count islands, explore each land cell and mark all connected land cells as visited using BFS or DFS, so each island is counted once.

Think of it like...

Imagine a group of islands on a map. You start on one island and walk around it, marking every part you visit so you don't count it again. Then you move to the next unvisited island and repeat.

Grid example:

  1 1 0 0 0
  1 1 0 0 0
  0 0 1 0 0
  0 0 0 1 1

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

Exploration:
Start at (0,0) -> mark connected land
Move to next unvisited land (2,2) -> mark
Move to next unvisited land (3,3) -> mark

Build-Up - 7 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 where each cell is either '1' (land) or '0' (water). An island is a group of '1's connected horizontally or vertically. Diagonal connections do not count. The goal is to count how many such islands exist.

Result

You can identify separate islands by looking at connected land cells.

Understanding the problem setup is key before applying any search technique.

2

Foundation

Basic Grid Traversal

Concept: Learn how to visit each cell in the grid systematically.

Use two nested loops to go through each row and column. For each cell, check if it is land and not visited. This sets the stage for exploring islands.

Result

You can scan the entire grid and identify candidate starting points for islands.

Systematic traversal ensures no cell is missed or counted twice.

3

Intermediate

Depth-First Search (DFS) Exploration

🤔Before reading on: Do you think DFS explores neighbors by going deep first or wide first? Commit to your answer.

Concept: Use DFS to explore all connected land cells starting from one cell.

When you find a land cell, use DFS to visit it and recursively visit all its unvisited land neighbors (up, down, left, right). Mark cells as visited to avoid repeats. This fully explores one island.

Result

After DFS, all cells of one island are marked visited, so the island is counted once.

DFS's deep exploration ensures you fully cover one island before moving on.

4

Intermediate

Breadth-First Search (BFS) Exploration

🤔Before reading on: Does BFS explore neighbors level by level or go deep first? Commit to your answer.

Concept: Use BFS to explore all connected land cells starting from one cell using a queue.

When you find a land cell, add it to a queue. While the queue is not empty, remove a cell, mark it visited, and add all unvisited land neighbors to the queue. This explores the island in layers.

Result

After BFS, all cells of one island are marked visited, counting the island once.

BFS explores neighbors evenly, which can be easier to implement iteratively.

5

Intermediate

Marking Visited Cells

Concept: Learn how to track which cells have been explored to avoid double counting.

Use a separate 2D boolean array or modify the original grid to mark visited land cells. This prevents revisiting the same island parts multiple times.

Result

Each island is counted exactly once, no overlaps.

Tracking visited cells is essential to correct counting and efficiency.

6

Advanced

Implementing DFS and BFS in C++

🤔Before reading on: Which data structure is better for DFS recursion, and which for BFS iteration? Commit to your answer.

Concept: Write complete C++ code for both DFS and BFS approaches to solve the problem.

Use recursion for DFS and a queue for BFS. Traverse the grid, call DFS/BFS on unvisited land cells, and increment island count. Mark visited cells during traversal.

Result

Correct count of islands printed for given grid input.

Knowing how to implement both methods in code solidifies understanding and prepares for real use.

7

Expert

Optimizations and Edge Cases

🤔Before reading on: Do you think modifying the input grid is safe or risky? Commit to your answer.

Concept: Explore how to optimize memory by modifying the grid and handle tricky cases like empty grids or all water.

Instead of extra memory, mark visited land cells by changing '1' to '0'. Handle empty grids by returning zero immediately. Consider grids with no land or all land.

Result

Efficient solution with minimal memory and robust handling of all inputs.

Understanding trade-offs between memory and input safety is key for production-ready code.

Under the Hood

Both DFS and BFS work by starting at a land cell and exploring all connected land cells. DFS uses a call stack (recursion) to go deep into neighbors before backtracking, while BFS uses a queue to explore neighbors level by level. Marking visited cells prevents infinite loops and double counting. The grid acts like a graph where each cell is a node connected to up to four neighbors.

Why designed this way?

DFS and BFS are classic graph traversal algorithms adapted to grids because grids can be seen as graphs with nodes and edges. They were chosen because they systematically explore all connected components, which matches the island counting problem. Alternatives like union-find exist but are more complex to implement for beginners.

Grid as graph:

┌───┬───┬───┬───┐
│1,1│1,2│0,3│0,4│
├───┼───┼───┼───┤
│1,5│1,6│0,7│0,8│
├───┼───┼───┼───┤
│0,9│0,10│1,11│0,12│
├───┼───┼───┼───┤
│0,13│0,14│1,15│1,16│
└───┴───┴───┴───┘

Edges connect horizontally and vertically adjacent '1's.

DFS stack or BFS queue explores these connected nodes fully.

Myth Busters - 4 Common Misconceptions

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

Common Belief: Some think diagonal neighbors count as connected land cells.

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

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

Quick: Can you use BFS and DFS interchangeably without any difference? Commit to yes or no.

Common Belief: BFS and DFS always produce the same traversal order and results.

Reality: They both find connected components but explore in different orders; BFS is level-wise, DFS is deep-first.

Why it matters: Traversal order affects performance and stack/queue usage, important for large grids.

Quick: Is it safe to skip marking visited cells? Commit to yes or no.

Common Belief: You can count islands without marking visited cells if you just check land cells.

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

Why it matters: Not marking visited leads to incorrect counts and infinite loops in traversal.

Quick: Does modifying the input grid always cause problems? Commit to yes or no.

Common Belief: Changing the input grid to mark visited cells is unsafe and should be avoided.

Reality: Modifying the input grid is a common and memory-efficient practice if input reuse is not needed.

Why it matters: Avoiding modification can lead to extra memory use; knowing when to modify helps optimize.

Expert Zone

1

DFS recursion depth can cause stack overflow on very large grids; iterative DFS or BFS is safer.

2

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

3

BFS can be faster in practice on some grids due to better cache locality and iterative nature.

When NOT to use

If the grid is extremely large or recursion depth is limited, avoid recursive DFS and prefer iterative BFS or union-find. For dynamic grids where islands change, incremental algorithms or union-find data structures are better.

Production Patterns

In real systems, BFS is often used for shortest path problems, while DFS is used for connectivity checks. For island counting, BFS is preferred in iterative environments, and union-find is used when multiple queries modify the grid.

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 theory and algorithms broadly.

Flood Fill Algorithm

Flood fill uses similar DFS/BFS techniques to fill connected areas in images.

Knowing flood fill helps understand how to explore and modify connected regions efficiently.

Epidemiology Spread Models

Exploring connected infected areas in a population grid uses similar BFS/DFS logic.

Techniques for counting islands can model disease spread clusters, showing cross-domain application.

Common Pitfalls

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

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 marking

Correct approach:

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

Root cause:

Forgetting to mark visited cells causes infinite recursion or double counting.

#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) explore(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 (auto d : directions) {
explore(r+d[0], c+d[1]);
}

Root cause:

Misunderstanding adjacency rules leads to merging separate islands.

#3 Using recursion without base case or boundary checks.

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);
}
}

Correct approach:

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

Root cause:

Missing boundary and visited checks causes crashes or infinite loops.

Key Takeaways

Number of Islands 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.

Marking visited cells is essential to prevent infinite loops and ensure correct counts.

Modifying the input grid to mark visited cells can save memory but may not always be safe.

Understanding adjacency rules and traversal order helps avoid common mistakes and optimize solutions.

Practice

1. What does the "Number of Islands" problem ask you to find in a 2D grid of '1's (land) and '0's (water)?

easy

A. Count total number of '1's in the grid

B. Count how many separate groups of connected '1's exist

C. Find the largest island size

D. Find the shortest path between two islands

Solution

1. Step 1: Understand the problem definition

   The problem asks to count distinct islands, where an island is a group of connected '1's horizontally or vertically.

2. Step 2: Clarify what is being counted

   We count how many separate clusters of '1's exist, not the total number of '1's or sizes.

3. Final Answer:

   Count how many separate groups of connected '1's exist -> Option B

4. Quick Check:

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

Hint: Islands = groups of connected '1's, count groups not cells [OK]

Common Mistakes:

• Counting total '1's instead of groups
• Including diagonal connections as connected
• Confusing island size with island count

2. Which of the following C++ code snippets correctly initializes a 2D vector grid of chars with given rows and columns filled with '0'?

easy

A. std::vector grid(rows, std::vector<char>(cols, '0'));

B. std::vector<char> grid(rows, std::vector<char>(cols, '0'));

C. std::vector grid(cols, std::vector<char>(rows, '0'));

D. std::vector grid(rows, cols, '0');

Solution

1. Step 1: Understand 2D vector initialization syntax

   To create a 2D vector of chars, use vector of vectors: outer vector size = rows, inner vector size = cols.

2. Step 2: Check each option

   std::vector grid(rows, std::vector<char>(cols, '0')); correctly creates 'rows' vectors each with 'cols' chars initialized to '0'. Others have wrong types or parameters.

3. Final Answer:

   std::vector grid(rows, std::vector<char>(cols, '0')); -> Option A

4. Quick Check:

   2D vector init = vector of vectors with sizes [OK]

Hint: Use vector(rows, vector<char>(cols, '0')) [OK]

Common Mistakes:

• Swapping rows and cols sizes
• Using wrong vector types
• Trying to initialize 2D vector with three parameters

3. Given the following grid and BFS-based code snippet to count islands, what is the output?

std::vector grid = {
  {'1','1','0','0'},
  {'1','0','0','1'},
  {'0','0','1','1'},
  {'0','0','0','0'}
};
int countIslands(const std::vector& grid) {
  int count = 0;
  int rows = grid.size();
  int cols = grid[0].size();
  std::vector visited(rows, std::vector<bool>(cols, false));
  std::queue> q;
  int directions[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
  for(int i=0; i=0 && nr=0 && nc

medium

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Identify islands in the grid

   Islands are groups of connected '1's. Here, islands are: top-left cluster (3 cells), single '1' at (1,3), and bottom cluster (2 cells at (2,2),(2,3)). Total 3 islands.

2. Step 2: Understand BFS traversal

   The BFS marks all connected '1's visited per island, so count increments once per island found.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Count islands = 3 [OK]

Hint: Count connected groups by BFS marking visited [OK]

Common Mistakes:

• Counting diagonal connections as islands
• Missing isolated '1's as separate islands
• Not marking visited correctly causing overcount

4. The following DFS code for counting islands has a bug. What is the bug?

void dfs(int r, int c, std::vector& grid) {
  int rows = grid.size();
  int cols = grid[0].size();
  if(r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] == '0')
    return;
  grid[r][c] = '0';
  dfs(r+1, c, grid);
  dfs(r-1, c, grid);
  dfs(r, c+1, grid);
  dfs(r, c-1, grid);
}

int numIslands(std::vector& grid) {
  int count = 0;
  for(int i=0; i

medium

A. The base case does not check for visited cells

B. The DFS does not check boundaries correctly

C. The DFS does not mark visited cells, causing infinite recursion

D. The grid is modified during DFS, which is incorrect

Solution

1. Step 1: Analyze DFS grid modification

   The DFS marks visited cells by changing '1' to '0' in the original grid, modifying input.

2. Step 2: Identify why this is a bug

   Modifying input grid may be unintended side effect; better to use a separate visited array to avoid altering input data.

3. Final Answer:

   The grid is modified during DFS, which is incorrect -> Option D

4. Quick Check:

   Modifying input grid = bug [OK]

Hint: Avoid changing input grid; use visited array instead [OK]

Common Mistakes:

• Ignoring that grid is changed in-place
• Assuming no visited tracking needed
• Misreading boundary checks as incorrect

5. You want to count islands in a grid where diagonal connections also count as connected (8 directions). How should you modify the BFS or DFS approach?

hard

A. Count islands by summing all '1's without traversal

B. Only check horizontal neighbors, ignore vertical and diagonal

C. Add diagonal directions (like (1,1), (1,-1), (-1,1), (-1,-1)) to the directions array

D. Use BFS for horizontal and DFS for vertical connections separately

Solution

1. Step 1: Understand connectivity change

   Diagonal connections mean neighbors include 8 directions: up, down, left, right, and 4 diagonals.

2. Step 2: Modify directions array

   Add diagonal moves (1,1), (1,-1), (-1,1), (-1,-1) to directions used in BFS or DFS to explore all connected neighbors.

3. Final Answer:

   Add diagonal directions (like (1,1), (1,-1), (-1,1), (-1,-1)) to the directions array -> Option C

4. Quick Check:

   Include all 8 neighbors for diagonal connectivity [OK]

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

Common Mistakes:

• Ignoring diagonal neighbors
• Counting only horizontal or vertical neighbors
• Trying to count without traversal