Surrounded Regions

Medium · Graphs

You are given a 2D grid of characters, each either 'X' or 'O'. Flip every 'O' to 'X' unless that 'O' is part of a group of connected O's (connected up, down, left, or right) that touches the border of the grid somewhere. Modify the grid in place; do not return anything.

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"]]
Why:    The blob of O's in the middle never touches the border so it gets flipped to X, but the lone O on the bottom border stays since it touches the edge.

Input:  board = [["X"]]
Output: [["X"]]
Why:    There are no O cells at all, so nothing changes.

Input:  board = [["O","O"],["O","O"]]
Output: [["O","O"],["O","O"]]
Why:    Every cell touches the border of this small grid, so none of the O's are captured.

Constraints

1 <= board.length, board[0].length <= 200, board[i][j] is 'X' or 'O'

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Surrounded Regions

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Surrounded Regions. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.