DFS and BFS Time and Space complexities of 'Number of islands' on Leetcode

Question

Here is the question description. The first 2 suggested solutions involve DFS and BFS. This question refers to the 1st two approaches: DFS and BFS. Apparently, the grid can be viewed as a graph.

I have included the problem statement here for easier reading.

Given a 2d grid map of '1's (land) and '0's (water), count the number of 
islands. An island is surrounded by water and is formed by connecting adjacent
lands horizontally or vertically. You may assume all four edges of the grid are 
all surrounded by water.

    Example 1:

    Input:
    11110
    11010
    11000
    00000

    Output: 1


    Example 2:

    Input:
    11000
    11000
    00100
    00011

    Output: 3

I am unclear as to why the time complexity for both DFS and BFS is O(rows * columns) for both. I see how this is the case where the grid is just full of 0's - we simply have to check each cell. However, doesn't the DFS approach add more time to the search? Even if we mark the cells we visited by changing them to 0 in the dfs methods, we still would revisit all the cells because of the two outer loops. If dfs could be have time complexity of O(n) in the case of a big grid with large row and column numbers, wouldn't the time complexity be O(rows * columns * max[rows, cols])? Moreover, isn't the same case with the BFS approach where it is O(rows * cols * possibleMaxSizeOfQueue) where possibleMaxSizeOfQueue could again be max[rows, cols]?

for (int r = 0; r < nr; ++r) {
      for (int c = 0; c < nc; ++c) {
        if (grid[r][c] == '1') {
          ++num_islands;
          dfs(grid, r, c);
        }
      }
    }

How is DFS's space complexity O(rows*cols)? Is it not possible/common to consider the call stack space as freed when a recursion branch returns? How is the space complexity for BFS O(min(rows, cols))? The way I see it, the queue could be full of all elements in the case of a grid with just 1's thereby giving O(rows*cols) for BFS space complexity.

DFS Solution

class Solution {
  void dfs(char[][] grid, int r, int c) {
    int nr = grid.length;
    int nc = grid[0].length;

    if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
      return;
    }

    grid[r][c] = '0';
    dfs(grid, r - 1, c);
    dfs(grid, r + 1, c);
    dfs(grid, r, c - 1);
    dfs(grid, r, c + 1);
  }

  public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) {
      return 0;
    }

    int nr = grid.length;
    int nc = grid[0].length;
    int num_islands = 0;
    for (int r = 0; r < nr; ++r) {
      for (int c = 0; c < nc; ++c) {
        if (grid[r][c] == '1') {
          ++num_islands;
          dfs(grid, r, c);
        }
      }
    }

    return num_islands;
  }
}

Time complexity : O(M×N) where M is the number of rows and N is the number of columns.

Space complexity : worst case O(M×N) in case that the grid map is filled with lands where DFS goes by M×N deep.

BFS Solution

class Solution {
  public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) {
      return 0;
    }

    int nr = grid.length;
    int nc = grid[0].length;
    int num_islands = 0;

    for (int r = 0; r < nr; ++r) {
      for (int c = 0; c < nc; ++c) {
        if (grid[r][c] == '1') {
          ++num_islands;
          grid[r][c] = '0'; // mark as visited
          Queue<Integer> neighbors = new LinkedList<>();
          neighbors.add(r * nc + c);
          while (!neighbors.isEmpty()) {
            int id = neighbors.remove();
            int row = id / nc;
            int col = id % nc;
            if (row - 1 >= 0 && grid[row-1][col] == '1') {
              neighbors.add((row-1) * nc + col);
              grid[row-1][col] = '0';
            }
            if (row + 1 < nr && grid[row+1][col] == '1') {
              neighbors.add((row+1) * nc + col);
              grid[row+1][col] = '0';
            }
            if (col - 1 >= 0 && grid[row][col-1] == '1') {
              neighbors.add(row * nc + col-1);
              grid[row][col-1] = '0';
            }
            if (col + 1 < nc && grid[row][col+1] == '1') {
              neighbors.add(row * nc + col+1);
              grid[row][col+1] = '0';
            }
          }
        }
      }
    }

    return num_islands;
  }
}

Time complexity : O(M×N) where M is the number of rows and N is the number of columns.

Space complexity : O(min(M,N)) because in worst case where the grid is filled with lands, the size of queue can grow up to min(M,N).

Answer 1

DFS takes linear time. It only visits each vertex once; it has an explicit check, before visiting a vertex, to see whether it has been visited before, and if so, avoid visiting it again. This should be covered in standard algorithms textbooks, so there is little point in repeating the standard analysis of DFS here -- I suggest finding a good textbook and reading their chapter on depth-first search. I like the discussion in Dasgupta, Papadimitriou, and Vazirani's textbook, but there are many others.

See also Counting islands in Boolean matrices for an even better algorithm that has the same asymptotic running time, but lower space complexity.