mediumGraphs

Surrounded Regions

Replace every O region that does not touch the board boundary with X. Connections are horizontal or vertical.

LeetCode ↗

Work through the cases

3 examples

Input notation

Rectangular rows containing only X and O, without spaces.

Expected result

The updated board in the same format.

Case 1

Input

XXXX
XOOX
XXOX
XOXX

Expected output

XXXX
XXXX
XXXX
XOXX

Case 2

Input

OO
OO

Expected output

OO
OO

Case 3

Input

Expected output

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Surrounded 'O's become 'X'; those connected to the border stay. m,n ≤ 200. Starting from interior cells to ask “am I surrounded?” must flood a whole component and is easy to get wrong on the border. Mark the unsurrounded cells instead. DFS from every border 'O', paint those cells with a placeholder, flip remaining 'O's to 'X', then restore the placeholders.

We can start from the boundary of the matrix, taking each 'O' on the matrix boundary as a starting point, and perform depth-first search. All 'O's found in the search are replaced with '.'.

Then we traverse the matrix again, for each position:

- If it is '.', replace it with 'O'; - Otherwise, if it is 'O', replace it with 'X'.

The time complexity is O(m × n), and the space complexity is O(m × n). Here, m and n are the number of rows and columns in the matrix, respectively.

class Solution {
    private final int[] dirs = {-1, 0, 1, 0, -1};
    private char[][] board;
    private int m;
    private int n;

    public void solve(char[][] board) {
        m = board.length;
        n = board[0].length;
        this.board = board;
        for (int i = 0; i < m; ++i) {
            dfs(i, 0);
            dfs(i, n - 1);
        }
        for (int j = 0; j < n; ++j) {
            dfs(0, j);
            dfs(m - 1, j);
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == '.') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }

    private void dfs(int i, int j) {
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') {
            return;
        }
        board[i][j] = '.';
        for (int k = 0; k < 4; ++k) {
            dfs(i + dirs[k], j + dirs[k + 1]);
        }
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.