Surrounded Regions

MediumGraphsborder dfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an m x n grid board whose cells each hold one of two characters: 'X' or 'O'. A region of 'O' cells is said to be **captured** if it is completely surrounded by 'X' cells. In other words, an 'O' cell survives only if it can reach the border of the grid by moving through other 'O' cells in the four cardinal directions (up, down, left, right). Any 'O' that is connected — directly or through a chain of neighboring 'O' cells — to a cell on the edge of the grid is **not** captured. Modify the grid so that every captured 'O' is flipped to 'X', while every 'O' that is connected to the border stays as 'O'. Return the resulting grid. Diagonal adjacency does not count: only the four orthogonal neighbors connect cells.

Examples

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"]]
The three `'O'` cells in the middle are fully enclosed by `'X'`, so they are captured and become `'X'`. The lone `'O'` in the bottom row sits on the border, so it survives.
Input: board = [["X"]]
Output: [["X"]]
A single cell with no `'O'` is unchanged.
Input: board = [["O","O"],["O","O"]]
Output: [["O","O"],["O","O"]]
Every cell touches the border, so nothing is captured.

Constraints

  • `m == board.length`
  • `n == board[i].length`
  • `1 <= m, n <= 200`
  • `board[i][j]` is either `'X'` or `'O'`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.