Number of Islands BFS and DFS in DSA C - Time & Space Complexity

Time Complexity: Number of Islands BFS and DFS

O(rows * cols)

Understanding Time Complexity

We want to understand how the time needed to find islands grows as the grid size increases.

How does the number of cells affect the work done by BFS or DFS?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

int numIslands(char** grid, int rows, int cols) {
    int count = 0;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == '1') {
                dfs(grid, i, j, rows, cols);
                count++;
            }
        }
    }
    return count;
}
    

This code counts islands by running DFS on each land cell and marking connected land as visited.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: DFS visits each cell connected to land once.
• How many times: Each cell is visited at most once during DFS or the main loops.

How Execution Grows With Input

As the grid size grows, the number of cells to check grows too.

Input Size (n = rows * cols)	Approx. Operations
10	About 10 visits
100	About 100 visits
1000	About 1000 visits

Pattern observation: The work grows roughly in direct proportion to the number of cells.

Final Time Complexity

Time Complexity: O(rows * cols)

This means the time needed grows linearly with the total number of cells in the grid.

Common Mistake

[X] Wrong: "DFS runs for each land cell separately, so time is O((rows*cols)^2)"

[OK] Correct: Each cell is visited only once because visited cells are marked, so DFS does not repeat work.

Interview Connect

Understanding how DFS or BFS explores grids efficiently is a key skill for many problems involving connected components.

Self-Check

"What if the grid was very sparse with few land cells? How would that affect the time complexity?"