# Java DFS + boundary cell turning solution, simple and clean code, commented.

• ``````public void solve(char[][] board) {
if (board.length == 0 || board[0].length == 0)
return;
if (board.length < 2 || board[0].length < 2)
return;
int m = board.length, n = board[0].length;
//Any 'O' connected to a boundary can't be turned to 'X', so ...
//Start from first and last column, turn 'O' to '*'.
for (int i = 0; i < m; i++) {
if (board[i][0] == 'O')
boundaryDFS(board, i, 0);
if (board[i][n-1] == 'O')
boundaryDFS(board, i, n-1);
}
//Start from first and last row, turn '0' to '*'
for (int j = 0; j < n; j++) {
if (board[0][j] == 'O')
boundaryDFS(board, 0, j);
if (board[m-1][j] == 'O')
boundaryDFS(board, m-1, j);
}
//post-prcessing, turn 'O' to 'X', '*' back to 'O', keep 'X' intact.
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O')
board[i][j] = 'X';
else if (board[i][j] == '*')
board[i][j] = 'O';
}
}
}
//Use DFS algo to turn internal however boundary-connected 'O' to '*';
private void boundaryDFS(char[][] board, int i, int j) {
if (i < 0 || i > board.length - 1 || j <0 || j > board[0].length - 1)
return;
if (board[i][j] == 'O')
board[i][j] = '*';
if (i > 1 && board[i-1][j] == 'O')
boundaryDFS(board, i-1, j);
if (i < board.length - 2 && board[i+1][j] == 'O')
boundaryDFS(board, i+1, j);
if (j > 1 && board[i][j-1] == 'O')
boundaryDFS(board, i, j-1);
if (j < board[i].length - 2 && board[i][j+1] == 'O' )
boundaryDFS(board, i, j+1);
}``````

• you can replace:
"if (i < 0 || i > board.length - 1 || j <0 || j > board[0].length - 1)
return;
if (board[i][j] == 'O')
board[i][j] = '';" to "board[i][j] = '';"
because you did the validity check before branching.

• I have the similar idea, but I implemented in C++. It turned out this solution gives run time error, which I think the problem is stack overflow.

• Actually your solution is fine, I use i < board.length - 1 instead of i < board.length - 2, which incurs too deep recursion.

• This solution is almost stack overflow. That i < board.length-2 saved you.

• Like your solution, concise and easy-understanding!

• Can someone please explain the specific reason behind " i <board.length-2" / " j <board[0].length - 2" ?

• @aritra90tnp because you don't need to visit the four boundary columns and rows again
you started dfs from them

• DFS using < board.length - 2 is a clever way to avoid stackoverflow in the test case, where it puts a ring of 'O' at the boundary to create a deep recursion and flag stackoverflow. It works in logic because we will visit this boundary cell anyway.

However, I doubt it would be working if we use a testcase that shifts the ring a bit inwards. It seems to me it will hit the same stack overflow issue.

• Could someone tell me why it's stackoverflow?

``````public void solve(char[][] board){
if(board==null||board.length<=2||board[0].length<=2)
return;
int row=board.length-1;
int col=board[0].length-1;
for(int i=0;i<=row;i++){
if(board[i][0]=='O')
DFS(board,i,0);
if(board[i][col]=='O')
DFS(board,i,col);
}
for(int j=0;j<=col;j++){
if(board[0][j]=='O')
DFS(board,0,j);
if(board[row][j]=='O')
DFS(board,row,j);
}

for(int i=0;i<=row;i++){
for(int j=0;j<=col;j++){
if(board[i][j]=='O')
board[i][j]='X';
else if(board[i][j]=='1')
board[i][j]='O';
}
}
}
public void DFS(char[][] board,int i,int j){
if(i<0||j<0||i>=board.length||j>=board[0].length||board[i][j]!='O')
return;
board[i][j]='1';
DFS(board,i,j+1);
DFS(board,i,j-1);
DFS(board,i-1,j);
DFS(board,i+1,j);
}``````

• @futurehau It's true using i>1 and i<board.length-2 could avoid the border.But it really makes a big difference?

``````public void DFS(char[][] board,int i,int j){
if(board[i][j]!='O')
return;
board[i][j]='1';
if(i>1)
DFS(board,i-1,j);
if(j>1)
DFS(board,i,j-1);
if(i<board.length-2)
DFS(board,i+1,j);
if(j<board[0].length-2)
DFS(board,i,j+1);
}``````

• public class Solution {

``````public void solve(char[][] board) {
int rows = board.length;
if (rows < 2) return;

int cols = board[0].length;

for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if ((i == 0 || j == 0 || i == rows - 1 || j == cols - 1) && board[i][j] == 'O') {
DFS(board, i, j);
}
}
}

for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
} else if (board[i][j] == '1') {
board[i][j] = 'O';
}
}
}
}

private void DFS(char[][] board, int i, int j) {
int rows = board.length;
int cols = board[0].length;
board[i][j] = '1';
int[] dx = {-1, 0, 0, 1};
int[] dy = {0, -1, 1, 0};

for (int k = 0; k < dx.length; k++) {
int x = dx[k] + i;
int y = dy[k] + j;
if (x > 0 && x < rows - 1 && y > 0 && y < cols - 1 && board[x][y] == 'O') {
DFS(board, x, y);
}
}
}
``````

}

• Share my python version for the convenience.

``````class Solution(object):
def solve(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
if not board or len(board) < 2 or len(board[0]) < 2:
return
m, n = len(board), len(board[0])

for i in xrange(m):
if board[i][0] == 'O' : self.dfs(board, i, 0)
if board[i][n-1] == 'O': self.dfs(board, i, n-1)
for j in xrange(n):
if board[0][j] == 'O': self.dfs(board, 0, j)
if board[m-1][j] == 'O': self.dfs(board, m-1, j)

for i in xrange(m):
for j in xrange(n):
if board[i][j] == 'O': board[i][j] = 'X'
elif board[i][j] == '*': board[i][j] = 'O'

def dfs(self, board, i, j):
if board[i][j] != 'O':
return
board[i][j] = '*'
if i > 1:
self.dfs(board, i-1, j)
if j > 1:
self.dfs(board, i, j-1)
if i < len(board) - 2:
self.dfs(board, i+1, j)
if j < len(board[0]) - 2:
self.dfs(board, i, j+1)
``````

• Best solution for this problem! Very straight-forward and clean code for quickly understanding the solution. Kudos.

• Whats wrong in this code. For some reason it gives stackOverFlow:
public class Solution {
int max_row = 0;
int max_col = 0;
final char VALID = 'X';
final char INVALID = 'O';
final char VISITED = '1';
public void solve(char[][] matrix) {
if (matrix == null) {
return;
}

``````    max_row = matrix.length;
if (max_row != 0) {
max_col = matrix[0].length;
}

// Top and bottom rows
for(int i = 0; i < max_col; i++) {
dfs(0, i, matrix);
dfs(max_row - 1, i, matrix);
}

// Left and right column
for(int i = 0; i < max_row; i++) {
dfs(i, 0, matrix);
dfs(i, max_col - 1, matrix);
}

for(int i = 0; i < max_row; i++) {
for(int j = 0; j < max_col; j++) {
if (matrix[i][j] == VISITED) {
matrix[i][j] = INVALID;
} else if (matrix[i][j] == INVALID) {
matrix[i][j] = VALID;
}
}
}
}

void dfs(int row, int col, char[][] matrix) {
if (row < 0 || col < 0 || row >= max_row || col >= max_col) {
return;
}

if ((matrix[row][col] == VISITED) || matrix[row][col] == VALID) {
return;
}

matrix[row][col] = VISITED;
dfs(row - 1, col, matrix);
dfs(row + 1, col, matrix);
dfs(row, col - 1, matrix);
dfs(row, col + 1, matrix);
}
``````

}

• Help wanted.
I implemented DFS + boundary cell turning solution in python. But it exceeds the max limits of recursion calls. Can anyone help me optimize my code? Thanks!

``````class Solution(object):
def solve(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
if not board or len(board) < 2 or len(board[0]) < 2:
return
self.directions = [(1,0), (-1,0), (0,1), (0,-1)]
m, n = len(board), len(board[0])

# start from boundary
for i in range(m):
if board[i][0]   == "O": self.dfs(board, i, 0, m, n)
if board[i][n-1] == "O": self.dfs(board, i, n-1, m, n)
for j in range(n):
if board[0][j]   == "O": self.dfs(board, 0, j, m, n)
if board[m-1][j] == "O": self.dfs(board, m-1, j, m, n)

# all * -> 0, all 0 -> X
for i , j in [(x, y) for x in range(m) for y in range(n)]:
if board[i][j] == 'O': board[i][j] = 'X'
elif board[i][j] == '*': board[i][j] = 'O'

def dfs(self, board, i, j, m, n):
board[i][j] = "*"
for dir in self.directions:
x, y = i + dir[0], j + dir[1]
if x < 0 or x >= m or y < 0 or y >= n or board[x][y] != "O":
continue
self.dfs(board, x, y, m, n)
``````

• @mo10 I tried an old (normal) way to dfs, leave me stackoverflow.....

• Seems like people are getting lots of stack overflow issues. If you switch to BFS (instead of DFS) you should reduce your memory footprint. Of course you'll need to use a queue instead of stack or recursion.

• This result might end up having stack over flow if the test case is changes a bit.

• I have the same idea with you, but more concise

``````public void solve(char[][] board) {
if (board.length < 3) return;
int h = board.length, w = board[0].length;

for (int i = 0; i < h; i++) {
if (board[i][0] == 'O') filter(i, 0, h, w, board);
if (board[i][w-1] == 'O') filter(i, w-1, h, w, board);
}

for (int j = 1; j < w-1; j++) {
if (board[0][j] == 'O') filter(0, j, h, w, board);
if (board[h-1][j] == 'O') filter(h-1, j, h, w, board);
}

for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (board[i][j] == 'O') board[i][j] = 'X';
else if (board[i][j] == 'N') board[i][j] = 'O';
}
}
}

private void filter(int i, int j, int h, int w, char[][] board) {
if (board[i][j] != 'O') return;
board[i][j] = 'N';
if (i > 1 ) filter(i-1, j, h, w, board);
if (i < h-2 ) filter(i+1, j, h, w, board);
if (j > 1 ) filter(i, j-1, h, w, board);
if (j < w - 2 ) filter(i, j+1, h, w, board);
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.