1
// time O(n * m) | space O(1)
2

3
// We essentially invert this question
4
// Instead of looking whether an 'O' node is surrounded,
5
// we check if an 'O' node is on the edge (outer layer can't be surrounded)
6
// and check if that is connected with any other nodes 'O' nodes (top, down, left, right).
7
// We do no care if it is not connected to an 'O' edge node and thus never dfs for it.
8
var solve = function (board) {
9
  if (!board.length) return [];
10

11
  for (let i = 0; i < board.length; i++) {
12
    for (let j = 0; j < board[0].length; j++) {
13
      // Only dfs if an 'O' and on the edge
14
      if (
15
        board[i][j] === "O" &&
16
        (i === 0 ||
17
          i === board.length - 1 ||
18
          j === 0 ||
19
          j === board[0].length - 1)
20
      ) {
21
        dfs(i, j);
22
      }
23
    }
24
  }
25

26
  for (let i = 0; i < board.length; i++) {
27
    for (let j = 0; j < board[0].length; j++) {
28
      if (board[i][j] === "V") {
29
        board[i][j] = "O";
30
      } else {
31
        board[i][j] = "X";
32
      }
33
    }
34
  }
35

36
  return board;
37

38
  function dfs(r, c) {
39
    if (
40
      r < 0 ||
41
      r >= board.length ||
42
      c < 0 ||
43
      c >= board[0].length ||
44
      board[r][c] === "X" ||
45
      board[r][c] === "V"
46
    ) {
47
      return;
48
    }
49

50
    board[r][c] = "V";
51

52
    dfs(r + 1, c);
53
    dfs(r - 1, c);
54
    dfs(r, c - 1);
55
    dfs(r, c + 1);
56
  }
57
};