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:
- Perform a
DFS
by attempting to visit a surrounding neighbor - See if the cell we're in meets this condition
- If yes, repeat step 1 for its neighbors
- 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:
xxxxxxxxxx
28
def flood_fill(matrix, x, y, new_val):
# Check if the source is already in desired color
old_value = matrix[x][y]
if new_val == old_value:
return matrix
# Stack is used for iterative DFS
# Start from the source (x,y)
stack = [(x,y)]
​
# While the stack is not empty
while stack:
row, col = stack.pop()
# We move at 8 directions.
# So we make a list and make these 8 cells iteratively
for dirx in [-1, 0, 1]:
for diry in [-1, 0, 1]:
# Ignore dir=(0,0)
if dirx == 0 and diry == 0:
continue
cell = (row+diry, col+dirx)
# Check if the cells are within grid
if cell[0] >= 0 and cell[0] < len(matrix) and cell[1] >= 0 and cell[1] < len(matrix[0]):
# Check if cell is in old_value
if matrix[cell[0]][cell[1]] == old_value:
matrix[cell[0]][cell[1]] = new_val
stack.append(cell)
​
return matrix
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment