Mark As Completed Discussion

What if we didn't want to use a queue? We can use a recursive depth-first search approach.

The idea here is to use some form of graph traversal mechanism to ensure we cover all necessary vertices within the graph that suit our conditions. Specifically, we are looking for vertices that match our origin point.

With that said, the pseudocode could be as simple as:

  1. Perform a DFS by attempting to visit a surrounding neighbor
  2. See if the cell we're in meets this condition
  3. If yes, repeat step 1 for its neighbors
  4. If not, no-op and don't do anything

Complexity of Final Solution

Let |V|, |E| represent the number of vertices and edges of the graph, respectively. A DFS for a graph implemented as a 2d matrix has O(|V|) time complexity, and O(|V|) space complexity as in the worst case, we can have |V| recursive calls being stored on the call-stack.

We are also giving the iterative solution using stack in DFS below:

PYTHON
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment