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


  • 1
    R

    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) {
           LinkedList<Point> queue = new LinkedList<>();
           Point point =  new Point(i, j);
           board[i][j] = temp;
           queue.add(point);
           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;
                       queue.add(new Point(i-1, j));
                   }
               }
               if (i+1 < board.length) {
                   if (board[i+1][j] == 'O') {
                       board[i+1][j] = temp;
                       queue.add(new Point(i+1, j));
                   }
               }
               if (j-1 >= 0) {
                   if (board[i][j-1] == 'O') {
                       board[i][j-1] = temp;
                       queue.add(new Point(i, j-1));
                   }
               }
                if (j+1 < board[0].length) {
                   if (board[i][j+1] == 'O') {
                       board[i][j+1] = temp;
                       queue.add(new Point(i, j+1));
                   }
               }
           }
       }
      

      }


  • 1
    H

    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


  • 0
    R

    Yes. You are right


  • 0
    C

    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).


Log in to reply
 

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