Easy understand java solution done in 2 pass

  • 2

    public class Solution {

    public void solve(char[][] board) {
        if(board.length==0) return;
        for(int i=0;i<board[0].length;i++) helper(board,0,i);
        for(int i=1;i<board.length;i++) helper(board,i,board[0].length-1);
        for(int i=0;i<board[0].length-1;i++) helper(board,board.length-1,i);
        for(int i=1;i<board.length-1;i++) helper(board,i,0);
        for(int i =0;i<board.length;i++)
            for(int j=0;j<board[0].length;j++)
                board[i][j] = (board[i][j]=='M')?'O':'X';
    public void helper(char[][] board, int a, int b){
        if(board[a][b]=='X'||board[a][b]=='M') return;
        board[a][b] = 'M';
        if(a+1<board.length) helper(board,a+1,b); 
        if(a-1>0) helper(board,a-1,b);
        if(b+1<board[0].length) helper(board,a,b+1);
        if(b-1>0) helper(board,a,b-1);


  • 0

    In first pass generate all un-surrounded regions and mark it as 'M'. In second pass set all 'M' to 'O' and all others to 'X'.

Log in to reply

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