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

Given an m x n matrix filled with 'X' and 'O', capture all regions that are completely surrounded by 'X'. A region of 'O' is captured by flipping all 'O's into 'X's in that surrounded region. An 'O' on the border or connected to a border 'O' cannot be captured. Return the modified matrix.

Example:

Input: [["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"]]
Sample Input
—
Sample Output
—
Constraints
  • 1 <= m, n <= 200
  • board[i][j] is 'X' or 'O'
Test Cases
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"]]
Topics
MatrixBFSDFS

Approach: Border DFS

First DFS from all border 'O's and mark them as safe ('S'). Then iterate through the entire board: convert remaining 'O's to 'X' (they are surrounded), and convert 'S' back to 'O'.

function givenAMatrixOfOAndXReplaceOWithXIfSurroundedByX(board) {
  if (!board.length) return board;
  const m = board.length, n = board[0].length;
  function dfs(r, c) {
    if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] !== "O") return;
    board[r][c] = "S";
    dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1);
  }
  for (let i = 0; i < m; i++) { dfs(i, 0); dfs(i, n-1); }
  for (let j = 0; j < n; j++) { dfs(0, j); dfs(m-1, j); }
  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++)
      board[i][j] = board[i][j] === "S" ? "O" : "X";
  return board;
}

Time Complexity: O(m × n)

Space Complexity: O(m × n) for recursion stack

Saved in this browser only. Private to you.

JavaScript