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.