Surrounded Regions

Problem

Given a grid of "X" and "O", flip every "O" that is completely surrounded by "X"s into an "X". A region touching the border is NOT surrounded.

Constraints

• 1 ≤ rows, cols ≤ 200

Approach — Graphs

This is a Graphs problem. The idea: explore the graph with BFS or DFS, marking nodes visited so you never process one twice. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(V + E) time.

Solution code

Python

class Solution:
    def solve(self, board):
        if not board:
            return board
        m, n = len(board), len(board[0])
        def dfs(r, c):
            if 0 <= r < m and 0 <= c < n and board[r][c] == 'O':
                board[r][c] = '#'
                for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                    dfs(r+dr, c+dc)
        for i in range(m):
            dfs(i, 0); dfs(i, n-1)
        for j in range(n):
            dfs(0, j); dfs(m-1, j)
        for i in range(m):
            for j in range(n):
                board[i][j] = 'O' if board[i][j] == '#' else 'X'
        return board

Java

class Solution {
    public void solve(char[][] board) {
        int rows = board.length;
        int cols = board[0].length;

        // Mark every 'O' connected to the border with a sentinel '#'.
        for (int r = 0; r < rows; r++) {
            dfs(board, r, 0);
            dfs(board, r, cols - 1);
        }
        for (int c = 0; c < cols; c++) {
            dfs(board, 0, c);
            dfs(board, rows - 1, c);
        }

        // Remaining 'O's are enclosed; flip them. Restore '#' to 'O'.
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (board[r][c] == 'O') {
                    board[r][c] = 'X';
                } else if (board[r][c] == '#') {
                    board[r][c] = 'O';
                }
            }
        }
    }

    private void dfs(char[][] board, int r, int c) {
        if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) {
            return;
        }
        if (board[r][c] != 'O') {
            return;
        }
        board[r][c] = '#';
        dfs(board, r + 1, c);
        dfs(board, r - 1, c);
        dfs(board, r, c + 1);
        dfs(board, r, c - 1);
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.