Given a matrix of ‘O’ and ‘X’, replace ‘O’ with ‘X’ if surrounded by ‘X’ Medium 0 attempts
GeeksforGeeks ↗

Given a matrix of ‘O’ and ‘X’, replace ‘O’ with ‘X’ if surrounded by ‘X’

Medium MatrixBFSDFS GeeksforGeeks

You're given an m x n board made up of the characters 'X' and 'O'. Any region of connected 'O' cells that is fully enclosed by 'X' cells should be captured — flip every 'O' in such a region over to 'X'. An 'O' sitting on the board's edge, or connected to one that is, is never considered enclosed and must stay as-is. Return the updated board.

Input Format
Implement givenAMatrixOfOAndXReplaceOWithXIfSurroundedByX(board). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output
[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]

Example 2

Input
board = [["O"]]
Output
[["O"]]
Constraints
  • 1 <= m, n <= 200
  • board[i][j] is 'X' or 'O'
Test Cases (2)
Case 1
Args: [[["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]] Expected: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Case 2
Args: [[["O"]]] Expected: [["O"]]
Topics
MatrixBFSDFS

Border Flood Fill

Only regions connected to a border survive. Mark all such cells safe with an iterative flood fill, then capture unmarked O cells.

javascript
function givenAMatrixOfOAndXReplaceOWithXIfSurroundedByX(board) {
  if(!board.length)return board;
  const rows=board.length,cols=board[0].length,stack=[];
  function visit(r,c){if(r>=0&&r<rows&&c>=0&&c<cols&&board[r][c]==='O'){board[r][c]='S';stack.push([r,c]);}}
  for(let r=0;r<rows;r++){visit(r,0);visit(r,cols-1);}for(let c=0;c<cols;c++){visit(0,c);visit(rows-1,c);}
  while(stack.length){const [r,c]=stack.pop();visit(r+1,c);visit(r-1,c);visit(r,c+1);visit(r,c-1);}
  for(let r=0;r<rows;r++)for(let c=0;c<cols;c++)board[r][c]=board[r][c]==='S'?'O':'X';
  return board;
}

Time: O(rows × cols) | Space: O(rows × cols)

Saved in this browser only. Private to you.

JavaScript