title: DFS and BFS Time and Space complexities of 'Number of islands' on Leetcode
body: <p><a href="https://leetcode.com/problems/number-of-islands/description/" rel="noreferrer">Here</a> is the question description. The first 2 suggested solutions involve <a href="https://leetcode.com/problems/number-of-islands/solution/" rel="noreferrer">DFS and BFS</a>. This question refers to the 1st two approaches: DFS and BFS. </p>
  
  <p>I have included the problem statement here for easier reading. </p>
  
  <pre><code>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
  </code></pre>
  
  <p>I am unclear as to why the time complexity for both DFS and BFS is <code>O(rows * columns)</code> 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 <code>0</code> 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 <code>O(rows * cols * possibleMaxSizeOfQueue)</code> where <code>possibleMaxSizeOfQueue</code> could again be <code>max[rows, cols]</code>? </p>
  
  <pre><code>for (int r = 0; r &lt; nr; ++r) {
        for (int c = 0; c &lt; nc; ++c) {
          if (grid[r][c] == '1') {
            ++num_islands;
            dfs(grid, r, c);
          }
        }
      }
  </code></pre>
  
  <p>How is DFS's space complexity <code>O(rows*cols)</code>? 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 <code>O(min(rows, cols))</code>? 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 <code>O(rows*cols)</code> for BFS space complexity. </p>
  
  <p><strong>DFS Solution</strong></p>
  
  <pre><code>class Solution {
    void dfs(char[][] grid, int r, int c) {
      int nr = grid.length;
      int nc = grid[0].length;
  
      if (r &lt; 0 || c &lt; 0 || r &gt;= nr || c &gt;= 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 &lt; nr; ++r) {
        for (int c = 0; c &lt; nc; ++c) {
          if (grid[r][c] == '1') {
            ++num_islands;
            dfs(grid, r, c);
          }
        }
      }
  
      return num_islands;
    }
  }
  </code></pre>
  
  <blockquote>
    <p>Time complexity : O(M×N) where M is the number of rows
    and N is the number of columns.</p>
    
    <p>Space complexity : worst case O(M×N) in case that the
    grid map is filled with lands where DFS goes by M×N deep.</p>
  </blockquote>
  
  <p><strong>BFS Solution</strong></p>
  
  <pre><code>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 &lt; nr; ++r) {
        for (int c = 0; c &lt; nc; ++c) {
          if (grid[r][c] == '1') {
            ++num_islands;
            grid[r][c] = '0'; // mark as visited
            Queue&lt;Integer&gt; neighbors = new LinkedList&lt;&gt;();
            neighbors.add(r * nc + c);
            while (!neighbors.isEmpty()) {
              int id = neighbors.remove();
              int row = id / nc;
              int col = id % nc;
              if (row - 1 &gt;= 0 &amp;&amp; grid[row-1][col] == '1') {
                neighbors.add((row-1) * nc + col);
                grid[row-1][col] = '0';
              }
              if (row + 1 &lt; nr &amp;&amp; grid[row+1][col] == '1') {
                neighbors.add((row+1) * nc + col);
                grid[row+1][col] = '0';
              }
              if (col - 1 &gt;= 0 &amp;&amp; grid[row][col-1] == '1') {
                neighbors.add(row * nc + col-1);
                grid[row][col-1] = '0';
              }
              if (col + 1 &lt; nc &amp;&amp; grid[row][col+1] == '1') {
                neighbors.add(row * nc + col+1);
                grid[row][col+1] = '0';
              }
            }
          }
        }
      }
  
      return num_islands;
    }
  }
  </code></pre>
  
  <blockquote>
    <p>Time complexity : O(M×N) where M is the number of rows
    and N is the number of columns.</p>
    
    <p>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).</p>
  </blockquote>