surrounded regions [M]

Since I’m still painfully unemployed, I’ve decided that doing one Neetcode problem per day is a decently good idea. Surrounded regions is the first problem of this series.

the problem

“You are given a 2-D matrix board containing X and O characters. If a continous, four-directionally connected group of Os is surrounded by Xs, it is considered to be surrounded. Change all surrounded regions of Os to Xs and do so in-place by modifying the input board.”

This problem might seem a little difficult at first glance. The first instinct is usually to mark all the Os that are surrounded by Xs. If you think about it for a little, you will likely realize that this is a rather difficult task to accomplish. Instead, we use the power of contradiction.

the power of contradiction

Instead of looking at the Os that are surrounded, we look at the Os that are NOT surrounded. That is, we mark the Os that are not surrounded by Xs, and turn everything else into an X. This is much easier.

The only time a group of Os is not surrounded by Xs is when it is touching the border. Thus, we just need to mark all the groups of Os that touch the border. This can be achieved by doing a depth-first search at every single O on the border.

dfs

For the DFS, we want check each adjacent cell recursively to see if it is an O. For every cell that is an O, we replace it with T so we know which ones are part of the unsurrounded group. We want break the recursion if the cell is either X or T. Below is a Python implementation.

def mark(r, c):
	if (r == ROWS or c == COLS or r < 0 or c < 0 or board[r][c] != "O"):
		return
	board[r][c] = "T"
	mark(r+1,c)
	mark(r, c+1)
	mark(r-1, c)
	mark(r, c-1)

After this, we simply loop through the matrix and turn everything else into an X. We also turn all the Ts back into Os.