My Java O(n^2) accepted solution

• The idea is pretty simple: a 'O' marked cell cannot be captured whether:

1. It is in contact with the border of the board or
2. It is adjacent to an unflippable cell.

So the algorithm is straightforward:

1. Go around the border of the board
2. When a 'O' cell is found mark it with 'U' and perform a DFS on its adjacent cells looking for other 'O' marked cells.
3. When the entire border is processed scan again the board
• If a cell is marked as 'O' it wasn't connected to unflippable cell. Hence capture it with 'X'
• If a cell is marked as 'X' nothing must be done.
• If a cell is marked as 'U' mark it as 'O' because it was an original 'O' marked cell which satisfied one of the above conditions.

On a technical side regarding the code:

• In the problem statement it's not specified that the board is rectangular. So different checks must performed when scanning the border.
• Since a pure recursive search causes stack overflow it's necessary to make the DFS iterative using a stack to simulate recursion.

public class Solution {

``````static class Pair {
public int first;
public int second;
public Pair(int f, int s) {
first = f;
second = s;
}
}

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

// modify the board
for(int i = 0; i < board.length; ++i) {
for(int j = 0; j < board[i].length; ++j) {
if(board[i][j] == 'O') {
board[i][j] = 'X';
} else if(board[i][j] == 'U') {
board[i][j] = 'O';
}
}
}
}

public void markUnflippable(char[][] board, int r, int c) {
int[] dirX = {-1,0,1,0};
int[] dirY = {0,1,0,-1};
ArrayDeque<Pair> stack = new ArrayDeque<>();
stack.push(new Pair(r,c));
while(!stack.isEmpty()) {
Pair p = stack.pop();
board[p.first][p.second] = 'U';
for(int i = 0; i < dirX.length; ++i) {
if(p.first + dirX[i] >= 0 && p.first + dirX[i] < board.length && p.second + dirY[i] >= 0 && p.second +dirY[i] < board[p.first + dirX[i]].length && board[p.first+dirX[i]][p.second+dirY[i]] == 'O') {
stack.push(new Pair(p.first+dirX[i],p.second+dirY[i]));
}
}
}
}
``````

}

• I have the same idea as you do. Cheers!

``````    public class Solution {
public void solve(char[][] board) {
if(board==null||board.length==0||board[0].length==0) return;
for(int i=0;i<board.length;i++){
for(int j=0;j<board[0].length;j++){
if(board[i][j]=='1') board[i][j] = 'O';
else if(board[i][j]=='O') board[i][j] = 'X';
else continue;
}
}
}
private void linkedUnit(char[][] board, int x, int y){
board[x][y] = '1';
}
}``````

• I implement BFS by implementing ArrayDeque as a queue, not stack. But limited time exceeds. Can someone explain this ?

• I suddenly feel your alg is BFS, rather than DFS...
Is my feeling right?

• No, I am wrong. It's DFS, you are right.

• Best solution

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