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


  • 53
    J
    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);
    }

  • 3
    U

    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.


  • 1
    X

    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.


  • 4
    X

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


  • 18
    M

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


  • 0
    B

    Like your solution, concise and easy-understanding!


  • 2
    A

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


  • 0
    T

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


  • 9
    W

    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.


  • 5
    F

    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);
    }

  • 1
    F

    @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);
    }

  • 2
    W

    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);
            }
        }
    }
    

    }


  • 0
    B

    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)
    

  • 0
    R

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


  • 0
    T

    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);
    }
    

    }


  • 0
    B

    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)
    

  • 0

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


  • 0

    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.


  • 0
    T

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


  • 0
    S

    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);
    }
    

Log in to reply
 

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