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:
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:
- Flood Fill question above,
- Maze where we have to find the shortest path from start to exit,
- 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:
- Is the space complexity of breadth first search on a grid: O(number_rows + number_cols)?
- Is the space complexity of depth first search on a grid: O(number_rows * number_cols)?