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 counting it, like exploring a forest patch completely before moving to the next.

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 islands (connected groups of 1s) are in the grid.

Step 1: Start scanning from top-left cell (0,0), found land (1), start DFS/BFS 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 its connected land to avoid counting again.

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

Visited cells now include (1,3), (2,2), (2,3)
Grid:
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++

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    int numIslands(vector<vector<int>>& grid) {
        int rows = grid.size();
        if (rows == 0) return 0;
        int cols = grid[0].size();
        int count = 0;
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));

        // Directions for neighbors: up, down, left, right
        vector<pair<int,int>> directions = {{-1,0},{1,0},{0,-1},{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++;
                    bfs(grid, visited, r, c, directions);
                }
            }
        }
        return count;
    }

    void bfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int r, int c, vector<pair<int,int>>& directions) {
        int rows = grid.size();
        int cols = grid[0].size();
        queue<pair<int,int>> q;
        q.push({r,c});
        visited[r][c] = true;

        while (!q.empty()) {
            auto [row, col] = q.front();
            q.pop();

            for (auto& d : directions) {
                int nr = row + d.first;
                int nc = col + d.second;

                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
                    grid[nr][nc] == 1 && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    q.push({nr,nc});
                }
            }
        }
    }
};

int main() {
    vector<vector<int>> grid = {
        {1,1,0,0},
        {1,1,0,1},
        {0,0,1,1}
    };
    Solution sol;
    cout << sol.numIslands(grid) << "\n";
    return 0;
}

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

Check for unvisited land to start new island search

count++;

Increment island count when new island found

bfs(grid, visited, r, c, directions);

Explore all connected land cells of this island

visited[r][c] = true;

Mark starting cell as visited

while (!q.empty()) {

Process all cells in current island using BFS

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

Check valid neighbor land cell not visited

visited[nr][nc] = true;

Mark neighbor as visited to avoid repeats

q.push({nr,nc});

Add neighbor to queue to continue BFS

Output

2

Complexity Analysis

Time: O(rows * cols) because each cell is visited once during BFS/DFS

Space: O(rows * cols) for the visited array and BFS queue in worst case

vs Alternative: Naive approach checking neighbors repeatedly would be slower; BFS/DFS ensures each cell is processed once efficiently.

Edge Cases

Empty grid

Returns 0 since no land exists

DSA C++

if (rows == 0) return 0;

Grid with all water (0s)

Returns 0 as no islands found

DSA C++

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

Grid with one big island (all 1s)

Returns 1 as all land is connected

DSA C++

visited[r][c] = true;

When to Use This Pattern

When you see a grid with connected components and need to count groups, use BFS or DFS to explore each group fully before moving on.

Common Mistakes

Mistake: Not marking visited cells, causing infinite loops or double counting
Fix: Mark cells as visited immediately when adding to queue or stack

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

Summary

Counts how many connected groups of land cells (islands) exist in a grid.

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

Explore all connected land cells from each unvisited land cell to count islands accurately.

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