Number of Islands BFS and DFS in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BFS-based Number of Islands

What is the output of the following C code that counts islands using BFS on a 4x5 grid?

DSA C

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

#define ROWS 4
#define COLS 5

void bfs(char grid[ROWS][COLS], bool visited[ROWS][COLS], int start_row, int start_col) {
    int directions[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
    int queue[ROWS*COLS][2];
    int front = 0, rear = 0;
    queue[rear][0] = start_row;
    queue[rear][1] = start_col;
    rear++;
    visited[start_row][start_col] = true;

    while(front < rear) {
        int r = queue[front][0];
        int c = queue[front][1];
        front++;
        for(int i=0; i<4; i++) {
            int nr = r + directions[i][0];
            int nc = c + directions[i][1];
            if(nr >= 0 && nr < ROWS && nc >= 0 && nc < COLS &&
               grid[nr][nc] == '1' && !visited[nr][nc]) {
                queue[rear][0] = nr;
                queue[rear][1] = nc;
                rear++;
                visited[nr][nc] = true;
            }
        }
    }
}

int numIslands(char grid[ROWS][COLS]) {
    bool visited[ROWS][COLS] = {false};
    int count = 0;
    for(int i=0; i<ROWS; i++) {
        for(int j=0; j<COLS; j++) {
            if(grid[i][j] == '1' && !visited[i][j]) {
                bfs(grid, visited, i, j);
                count++;
            }
        }
    }
    return count;
}

int main() {
    char grid[ROWS][COLS] = {
        {'1','1','0','0','0'},
        {'1','1','0','0','0'},
        {'0','0','1','0','0'},
        {'0','0','0','1','1'}
    };
    printf("%d\n", numIslands(grid));
    return 0;
}

A 4

B 3

C 2

D 1

💡 Hint

Count connected groups of '1's connected horizontally or vertically.

The grid has three separate islands: top-left block, middle single cell, and bottom-right block.

❓ Predict Output

intermediate

Output of DFS-based Number of Islands

What is the output of this C code that counts islands using DFS on a 3x3 grid?

DSA C

#include <stdio.h>
#include <stdbool.h>

#define ROWS 3
#define COLS 3

void dfs(char grid[ROWS][COLS], bool visited[ROWS][COLS], int r, int c) {
    if(r < 0 || r >= ROWS || c < 0 || c >= COLS || 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);
}

int numIslands(char grid[ROWS][COLS]) {
    bool visited[ROWS][COLS] = {false};
    int count = 0;
    for(int i=0; i<ROWS; i++) {
        for(int j=0; j<COLS; j++) {
            if(grid[i][j] == '1' && !visited[i][j]) {
                dfs(grid, visited, i, j);
                count++;
            }
        }
    }
    return count;
}

int main() {
    char grid[ROWS][COLS] = {
        {'1','0','1'},
        {'0','1','0'},
        {'1','0','1'}
    };
    printf("%d\n", numIslands(grid));
    return 0;
}

A 4

B 3

C 1

D 5

💡 Hint

Each '1' not connected horizontally or vertically counts as a separate island.

There are five '1's isolated diagonally, so 5 islands.

🧠 Conceptual

advanced

Why BFS or DFS is suitable for Number of Islands?

Which reason best explains why BFS or DFS is used to solve the Number of Islands problem?

A They use less memory than other algorithms like binary search.

B They sort the grid cells to find islands faster.

C They explore all connected land cells systematically to mark visited islands.

D They convert the grid into a tree structure automatically.

💡 Hint

Think about how connected parts of the grid are explored.

BFS and DFS traverse all connected land cells to mark an entire island visited, preventing double counting.

🔧 Debug

advanced

Identify the bug in this DFS code snippet for Number of Islands

What error does this DFS code cause when counting islands in a grid?

DSA C

void dfs(char grid[][5], bool visited[][5], int r, int c) {
    if(r < 0 || r >= 5 || c < 0 || c >= 5 || 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);
}

A Array index out of bounds error due to incorrect boundary check

B Stack overflow due to infinite recursion

C Visited array not updated causing infinite loop

D No error, code works correctly

💡 Hint

Check how the boundary conditions are written for row and column indices.

The condition 'r > 4' and 'c > 4' allows r or c to be 5, which is out of bounds for 0-4 indices.

🚀 Application

expert

Optimizing Number of Islands for Large Grids

Which approach best optimizes counting islands in a very large grid with mostly water cells?

A Use BFS/DFS but skip cells that are water to reduce unnecessary traversal

B Convert grid to graph and run Dijkstra's algorithm for shortest path

C Use bubble sort to order cells and then count islands

D Use recursion without visited array to save memory

💡 Hint

Think about avoiding work on water cells and marking visited land.

Skipping water cells and marking visited land reduces traversal and improves performance on large sparse grids.

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