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.

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' time complexity is proportional to the total number of vertexes and edges of the graph visited. In that case, there are N*M vertexes and slightly less than 4*N*M edges, their sum is still O(N*M).

Why so: because we process each edge exactly once in each direction. Situation where recursive call is immediately terminated does not matter as time spent for that call can be accounted for on the call site; and there is at most once call for each directed edge, hence O(N*M).

BFS' time complexity is quite similar. Maximal length of the queue does not matter at all because at no point we examine it in a whole. Queue only gets "append" and "remove first" queries, which can be processed in constant time regardless of queue's size. If we need to check whether a vertex was already visited, we do so in constant time.

Worst-case space complexity for DFS is Theta(N*M): just take any "snake-wise" maze:

......
#####.
......
.#####
......

Here DFS will be forced to traverse the path in whole before it stops and starts freeing up the stack. However, in no situation there will be more than N*M+1 elements on the stack.

Worst-case space complexity for BFS is indeed not O(max(N, M)): it's Theta(N*M) even when we're considering simple grid. Here is an example from math.stackexchange.com:

If we start BFS in the red point, it will end up with a queue which contains all leafs of the tree, their number is proportional to N*M. One can also truncate 3/4rd of the example and make the red dot appear in the upper-left corner.

Looks like the solution you've read is wrong in respect to BFS' worst case memory consumption.

Answer 2

@yeputons: I don't think the space complexity for BFS will be proportional to N * M. When you say a queue could have at max all the leaf elements (when starting at center) that actually means 2*(N+M) elements at Max.

And when starting from one of the corners it indeed is O(min(m, n)), because number of elements being added to the queue are constrained.