Accepted O(n) space, O(n *m) time, BFS Java solution

• Here is the idea:

1. loop the out layer, if found any 'O', do a BFS, mark any 'O' with a temp value, for example 'T'

2. loop the matrix again, flip 'T' to 'O', and flipt 'O' to 'X'.

public class Solution {
private static char temp = 'T';

`````` private class Point {
int i;
int j;

public Point(int i, int j) {
this.i = i;
this.j = j;
}
}

public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) {
return;
}

for (int j = 0; j<board[0].length; j++) {
if (board[0][j] == 'O') {
mark(board, 0, j);
}
}

for (int i = 1; i<board.length; i++) {
if (board[i][board[0].length-1] == 'O') {
mark(board, i, board[0].length-1);
}
}

if (board[0].length > 1) {
for (int j = board[0].length-2; j>-1; j--) {
if (board[board.length-1][j] == 'O') {
mark(board, board.length-1, j);
}
}
}

if (board.length>2) {
for (int i = board.length-2; i>0; i--) {
if (board[i][0] == 'O') {
mark(board, i, 0);
}
}
}

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

private void mark(char[][] board, int i, int j) {
Point point =  new Point(i, j);
board[i][j] = temp;
while (!queue.isEmpty() ) {
point = queue.remove();
i = point.i;
j = point.j;
if (i-1 >= 0) {
if (board[i-1][j] == 'O') {
board[i-1][j] = temp;
}
}
if (i+1 < board.length) {
if (board[i+1][j] == 'O') {
board[i+1][j] = temp;
}
}
if (j-1 >= 0) {
if (board[i][j-1] == 'O') {
board[i][j-1] = temp;
}
}
if (j+1 < board[0].length) {
if (board[i][j+1] == 'O') {
board[i][j+1] = temp;
}
}
}
}
``````

}

• if what you described is correct, then it's O(M+N) space i think, cause when you are doing the BFS, your queue may contains up to 2(M+N) objects

• Yes. You are right

• I think it's O(NM) space in worst case. for example if the input matrix are all 'O' without any 'X'. Then, the queue need to store the whole matrix, which is O(MN).

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