Number of Islands BFS and DFS in DSA Typescript - 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 search through the grid affect the total work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function numIslands(grid: string[][]): number {
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;

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

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count++;
        dfs(r, c);
      }
    }
  }
  return count;
}
    

This code counts islands by visiting each cell and using DFS to mark connected land.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Visiting each cell once and exploring neighbors via DFS.
• 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 grows linearly with the total number of cells in the grid.

Common Mistake

[X] Wrong: "DFS runs multiple times for each island, so time is more than linear."

[OK] Correct: Each cell is marked visited once, so DFS does not revisit cells, keeping total work linear.

Interview Connect

Understanding this helps you explain how graph traversal works on grids, a common interview skill.

Self-Check

"What if we used BFS instead of DFS? How would the time complexity change?"