# My java solution, not very concise but the idea is clear

• for each 'O' cell , try to see if the expanded area "borders on " the 4 sides, if so, recursively fills that patch with X. originally I coded the recursive "border check" and the "recursive fill" using plain recursion, but then got stack overflow for large instances. then I had to change the implementation to a stack. a queue would work similarly.

another post provides a better approach and directly tries to flip from the "O" cells on the border, so there is no "bordering check" anymore, 1 step finishes the job.

``````public class Solution {
int m;
int n;
public void solve(char[][] board) {
if (board == null || board.length == 0) return;
m = board.length;
if (board[0] == null) return;
n = board[0].length;
for(int i=0;i<m;i++) {
for(int j=0;j<n;j++) {
if ( (board[i][j] == 'O' ) )
if (recursiveBordering(board, i, j))
recursiveFlip(board, i,j, '2');
else
recursiveFlip(board, i,j, 'X');
}
}

for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
if (board[i][j] == '2')
board[i][j] = 'O';

}

boolean recursiveBordering(char[][]board, int i0, int j0) {
Stack<int[]> q = new Stack<int[]>();
q.push(new int[]{i0,j0});
while(!q.empty()) {

int []ij = q.pop();
int i = ij[0];
int j = ij[1];
boolean bordering = (i == 0 || i==m-1 || j==0 || j== n-1 ) && (board[i][j] == 'O' || board[i][j] == '1');

if (bordering) return true;

board[i][j] = '1';
if ( i<m-1 && board[i+1][j] == 'O')
q.push(new int[]{i+1,j});

if (i>0  && board[i-1][j] == 'O')
q.push(new int[]{i-1,j});

if (j<n-1 && board[i][j+1] == 'O')
q.push(new int[]{i,j+1});
if (j>0 && board[i][j-1] == 'O')
q.push(new int[]{ i,j-1});

}
return false;

}

void recursiveFlip(char [][]board, int i0, int j0, char c) {
Stack<int[]> q = new Stack<int[]>();
q.push(new int[]{i0,j0});
while(!q.empty()) {

int []ij = q.pop();
int i = ij[0];
int j = ij[1];
board[i][j] = c;

if (i <m-1 && ( board[i+1][j] == 'O' || board[i+1][j] == '1'))
q.push(new int[]{ i+1, j});
if (i >0 && ( board[i-1][j] == 'O' || board[i-1][j] == '1'))
q.push(new int[]{ i-1, j});
if (j <n-1 && ( board[i][j+1] == 'O' || board[i][j+1] == '1'))
q.push(new int[]{i, j+1});
if (j >0 && ( board[i][j-1] == 'O' || board[i][j-1] == '1'))
q.push(new int[]{ i, j-1});

}
}
``````

}

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