Surrounded Regions

Medium Problem 104 of 151 Java and Python

Problem

Given an m × n board of "X" and "O", capture every region of "O" cells that is surrounded by "X": flip all "O"s in such a region to "X", in place.

A region is surrounded if none of its cells is on the border of the board. Regions touching the border are never captured.

Example 1

Input: board = ["XXXX", "XOOX", "XXOX", "XOXX"]
Output: ["XXXX", "XXXX", "XXXX", "XOXX"]
Why: The bottom O touches the border, so it stays.

Example 2

Input: board = ["X"]
Output: ["X"]

Constraints

1 ≤ m, n ≤ 200

Explanation

Deciding "is this region surrounded?" for every region is awkward. The opposite is easy: any O connected to the border is safe. So DFS from every border O, marking reachable cells as safe (say S).

Afterwards, every remaining O is surrounded: flip it to X, and turn the S cells back into O.

Approach 1 · Naive

Check each region

Time O(m · n)
Space O(m · n)

For each unvisited O, collect its whole region with BFS and note whether any cell is on the border. Flip the region if not.

For each unvisited O, BFS its region, recording its cells and whether it touches the border.
If it does not, set all its cells to X.

Java

import java.util.*;

class Solution {
    public void solve(char[][] board) {
        int m = board.length;
        int n = board[0].length;
        boolean[][] seen = new boolean[m][n];
        int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] != 'O' || seen[i][j]) {
                    continue;
                }
                List<int[]> region = new ArrayList<>();
                boolean border = false;
                Deque<int[]> queue = new ArrayDeque<>();
                queue.add(new int[] { i, j });
                seen[i][j] = true;
                while (!queue.isEmpty()) {
                    int[] cell = queue.poll();
                    region.add(cell);
                    if (cell[0] == 0 || cell[1] == 0 || cell[0] == m - 1 || cell[1] == n - 1) {
                        border = true;
                    }
                    for (int[] d : dirs) {
                        int r = cell[0] + d[0];
                        int c = cell[1] + d[1];
                        if (r >= 0 && c >= 0 && r < m && c < n && board[r][c] == 'O' && !seen[r][c]) {
                            seen[r][c] = true;
                            queue.add(new int[] { r, c });
                        }
                    }
                }
                if (!border) {
                    for (int[] cell : region) {
                        board[cell[0]][cell[1]] = 'X';
                    }
                }
            }
        }
    }
}

Python

from collections import deque

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        m, n = len(board), len(board[0])
        seen = set()
        for i in range(m):
            for j in range(n):
                if board[i][j] != "O" or (i, j) in seen:
                    continue
                region, border = [], False
                queue = deque([(i, j)])
                seen.add((i, j))
                while queue:
                    r, c = queue.popleft()
                    region.append((r, c))
                    border |= r in (0, m - 1) or c in (0, n - 1)
                    for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                        if 0 <= nr < m and 0 <= nc < n and board[nr][nc] == "O" and (nr, nc) not in seen:
                            seen.add((nr, nc))
                            queue.append((nr, nc))
                if not border:
                    for r, c in region:
                        board[r][c] = "X"

Approach 2 · Optimal

Mark border-connected cells, then flip

Time O(m · n)
Space O(m · n) recursion worst case

DFS from every O on the border, marking those cells S. Then flip remaining O to X and S back to O.

For each border cell with O, run mark(r, c), which turns connected O cells into S.
Scan the board: O → X, S → O.

Java

class Solution {
    public void solve(char[][] board) {
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            mark(board, i, 0);
            mark(board, i, n - 1);
        }
        for (int j = 0; j < n; j++) {
            mark(board, 0, j);
            mark(board, m - 1, j);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = board[i][j] == 'S' ? 'O' : 'X';
            }
        }
    }

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

Python

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        m, n = len(board), len(board[0])

        def mark(r, c):
            if not (0 <= r < m and 0 <= c < n) or board[r][c] != "O":
                return
            board[r][c] = "S"
            mark(r + 1, c)
            mark(r - 1, c)
            mark(r, c + 1)
            mark(r, c - 1)

        for i in range(m):
            mark(i, 0)
            mark(i, n - 1)
        for j in range(n):
            mark(0, j)
            mark(m - 1, j)
        for i in range(m):
            for j in range(n):
                board[i][j] = "O" if board[i][j] == "S" else "X"

Complexity compared

Approach	Time	Space
Naive Check each region	O(m · n)	O(m · n)
Optimal Mark border-connected cells, then flip	O(m · n)	O(m · n) recursion worst case

Key takeaways

When the condition is about the border, start the search from the border.
Pacific Atlantic Water Flow uses the same reverse-from-the-edges idea.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem