# Is Breadth First Search Space Complexity on a Grid different?

Is the Space Complexity O(number_rows + number_cols) for Breadth First Search on a Grid. This is an attempt to show my reasoning:

For example, the flood fill question is described here:

https://www.geeksforgeeks.org/flood-fill-algorithm-implement-fill-paint/

The flood fill algorithm using breadth first search (queue) has space complexity: O(number_rows + number_cols).

Why? Suppose you start at the top left corner (or coordinate (0,0)). Going to the right we will get at most O(number_cols) in the queue. When we reached the end of the column we can then start going down from coordinate (0, 0) giving us O(number_cows + number_cols) in the queue.

Then, is it the case that many of the questions where we use breadth first search on a grid we will get space complexity of O(number_rows + number_cols). For example:

1. Flood Fill question above,
2. Maze where we have to find the shortest path from start to exit,
3. Finding number of islands (reference below)

But for 3) finding the number of islands, it looks like some people are saying the space complexity is O(number_rows * number_cols) from : https://stackoverflow.com/questions/50901203/dfs-and-bfs-time-and-space-complexities-of-number-of-islands-on-leetcode

On the other hand, I would assume that the space complexity of dfs on a grid is O(number_rows * number_cols)

The questions are as follows based on the above:

1. Is the space complexity of breadth first search on a grid: O(number_rows + number_cols)?
2. Is the space complexity of depth first search on a grid: O(number_rows * number_cols)?

Other references:

It depends what you mean by a "on a grid".

If you mean that you are working with the graph of a complete grid, with number_rows * number_cols vertices (one for each grid point) and an edge between every pair of adjacent vertices:

Yes, that's correct. The asymptotic time complexity of both is O(number_rows * number_cols), and the asymptotic space complexity is O(number_rows + number_cols) for BFS or O(number_rows * number_cols) for DFS.

If you mean that you are working with a graph that is a subgraph of a complete grid, then:

No, that's incorrect. The asymptotic time complexity of both is O(number_rows * number_cols), and the asymptotic space complexity of both could be as large as O(number_rows * number_cols), as explained in https://stackoverflow.com/a/50912382/781723.

• But what does this mean from 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. (from stackoverflow.com/questions/50901203/…)
– Meem
Mar 30, 2019 at 4:30
• Assume there are $c$ columns and $r$ rows. Each "node" (cell in grid) has 4 edges (left, right, up, down). This means there are $m = 4cr$ edges and $n = cr$ nodes. So it is still $O(\max(n, m))$. Don't mix up $c$ and $r$ with $n$ and $m$ as these are distinct and different values.
– ryan
Mar 30, 2019 at 5:10
• It is confusing because variables are being used without being defined. That's a recipe for confusion. I'm guessing that ryan intends that n = number of vertices, m = number of edges, r = number of rows, c = number of columns. As ryan explains, don't mix up $c$ and $r$ with $n$ and $m$. The term subgraph is defined in standard places, e.g., mathworld.wolfram.com/Subgraph.html or en.wikipedia.org/wiki/Glossary_of_graph_theory_terms#S.