title: Trying to understand why the Space Complexity of searching through a grid using BFS is O(m * n), where m is no. of rows and n is no. of cols
body: <p>I am trying to understand the space complexity of using BFS in a grid. When we start on a cell in a grid of m * n dimensions, we could go either up, right, down and left.</p>
  <p>My understanding is the Space Complexity should be O(m + n) if we start somewhere in the middle. If we start in one of the 4 corners it should be O(min(m, n)). So overall it could be O(m + n) in the worst case given we don't know where to start.</p>
  <p>I tried to test on my local by starting on all of the cells individually in a grid and calculate the max size of the queue and understand the Space Complexity.</p>
  <p>My test code:</p>
  <pre><code>class Solution {
  
      int max = 0;
  
      public static void main(String[] args) {
          Solution solution = new Solution();
  
          int rows = 200, cols = 200;
          int[][] grid = new int[rows][cols];
  
          for (int i = 0; i &lt; rows; i++) {
              for (int j = 0; j &lt; cols; j++) {
                  solution.initializeGrid(grid, rows, cols);
                  solution.processGrid(grid, rows, cols, i, j);
              }
          }
  
          System.out.println(&quot;Highest queue size is &quot; + solution.max);
      }
  
      private void initializeGrid(int[][] grid, int rows, int cols) {
          for (int i = 0; i &lt; rows; i++) {
              for (int j = 0; j &lt; cols; j++) {
                  grid[i][j] = 1;
              }
          }
      }
  
      private void processGrid(int[][] grid, int rows, int cols, int row, int col) {
          Queue&lt;int[]&gt; queue = new LinkedList&lt;&gt;();
          int[] childrenRows = new int[]{-1, 0, 1, 0};
          int[] childrenCols = new int[]{0, 1, 0, -1};
  
          queue.add(new int[]{row, col});
          grid[row][col] = 0;
  
          while (!queue.isEmpty()) {
              max = Math.max(max, queue.size());
  
              int[] parent = queue.poll();
              int pr = parent[0], pc = parent[1];
  
              for (int i = 0; i &lt; 4; i++) {
                  int cr = pr + childrenRows[i], cc = pc + childrenCols[i];
  
                  if (cr &gt;= 0 &amp;&amp; cr &lt; rows &amp;&amp; cc &gt;= 0 &amp;&amp; cc &lt; cols &amp;&amp; grid[cr][cc] == 1) {
                      queue.add(new int[]{cr, cc});
                      grid[cr][cc] = 0;
                  }
              }
          }
      }
  }
  </code></pre>
  <p>The output for the given input of m = 200, n = 200 is</p>
  <pre><code>The highest queue size is 399. This value proportional to O(m + n)
  </code></pre>
  <p>I know this is not the right way to calculate Space Complexity but I want to the know exact space used by the queue and if it's proportional to O(m * n) or not.</p>
  <p>I tried with other larger inputs. Still, the Space Complexity is O(m + n).</p>
  <p>Am I missing something here? Could someone please help me to understand the logic?</p>